61.有序数组的平方

day13： 977. 有序数组的平方（简单）

思路：

• 直接解法：先算平方再用sort方法
• 使用双指针1：因为数组是有序的，因此可以先将数组划分为两部分，大于0的部分和小于等于0的部分。然后，从中间开始往两头趋近，需要注意的是，需要判断左侧和右侧是否还有值，如果有值需要处理后续节点。
• 使用双指针2：和上面双指针定义的不同，第三种方法是从最左和最右两边开始比较的，因此不用考虑【判断左侧和右侧是否还有值】的情况。
  第一种方法：

var sortedSquares = function (nums) {
  let result = [];
  nums.forEach((item) => {
    result.push(Math.abs(item) * Math.abs(item));
  });
  return result.sort((a, b) => {
    return a - b;
  });
};

第二种方法：指针从中间趋于两边

var sortedSquares1 = function (nums) {
  let n = nums.length;
  //记录分界点
  let negative = -1;
  for (let i = 0; i < n; ++i) {
    if (nums[i] < 0) {
      negative = i;
    } else {
      break;
    }
  }
  //目标数组
  let ans = [];
  let index = 0,
    i = negative,
    j = negative + 1;
  //i<0左侧已经到头，j>=n右侧已经到头
  while (i >= 0 || j < n) {
    if (nums[i] * nums[i] >= nums[j] * nums[j]) {
      ans.push(nums[j] * nums[j]);
      j++;
    } else if (nums[i] * nums[i] < nums[j] * nums[j]) {
      ans.push(nums[i] * nums[i]);
      i--;
    } else if (i < 0) {
      // 处理右侧后续节点
      ans[index] = nums[j] * nums[j];
      j++;
    } else if (j >= n) {
      //处理左侧后续节点
      ans[index] = nums[i] * nums[i];
      i--;
    }
    ++index;
  }
  return ans;
};

第三种方法：

var sortedSquares2 = function (nums) {
  let n = nums.length,
    ans = [];
  for (let i = 0, j = n - 1, pos = n - 1; i <= j; ) {
//指针从两边趋于中间
    if (nums[i] * nums[i] > nums[j] * nums[j]) {
      ans[pos] = nums[i] * nums[i];
      ++i;
    } else {
      ans[pos] = nums[j] * nums[j];
      --j;
    }
    --pos;
  }
  return ans;
};