27. 有序数组的平方#

有序数组的平方-力扣链接

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

    输入：nums = [-4,-1,0,3,10]
    输出：[0,1,9,16,100]
    解释：平方后，数组变为 [16,1,0,9,100]
    排序后，数组变为 [0,1,9,16,100]
复制

示例 2：

    输入：nums = [-7,-3,2,3,11]
    输出：[4,9,9,49,121]
复制

提示：

    1 <= nums.length <= 104
    -104 <= nums[i] <= 104
    nums 已按 非递减顺序 排序
复制

进阶： 请你设计时间复杂度为 O(n) 的算法解决本问题

思路#

有序数组的平方，该题的解析思路为，采用双指针法，该输入数组是以从小到大的顺序排列，所有有可能是负数，负数的平方是正数所有有可能也是最大的，所以采用前后指针收缩区间，就可以节省排序的步骤，简化时间复杂度。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
  let newNums = [];
  let len = nums.length - 1;
  for (let i = 0, j = nums.length - 1; i <= j; ) {
    if (nums[i] * nums[i] > nums[j] * nums[j]) {
      newNums[len--] = nums[i] * nums[i];
      i++;
    } else {
      newNums[len--] = nums[j] * nums[j];
      j--;
    }
  }
  return newNums;
};

console.log(sortedSquares([-4, -1, 0, 3, 10]));

// 时间复杂度O(n)

复制