LeetCode-有序数组的平方

Last updated on 3 months ago

1.有序数组的平方

#给你一个按 非递减顺序 排序的整数数组 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

vector<int> sortedSquares(vector<int> &nums) {
  if (nums.size() == 1) {
    return {nums[0] * nums[0]};
  }
  int left = 0; 
  int right = nums.size() - 1;
  vector<int> ret;
  while (left <= right) {
    if (nums[right] * nums[right] >= nums[left] * nums[left]) {  //前后数值结果 比较，如果大取出来，移动指针  
      ret.push_back(nums[right] * nums[right]);
      right--;

    } else {
      ret.push_back(nums[left] * nums[left]); //同理
      left++;
    }
  }
  return ret;
}