LeetCode 之 有序数组的平方

算法模拟： Algorithm Visualizer

在线工具： C++ 在线工具

如果习惯性使用Visual Studio Code进行编译运行，需要C++11特性的支持，可参考博客：

VisualStudio Code 支持C++11插件配置

有序数组的平方

---

LeetCode 有序数组的平方

问题：

给你一个按 非递减顺序 排序的整数数组 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

思路：

使用双指针方法

首先，我们可以创建一个新的结果数组 result ，其大小与输入数组 nums 相同。

然后，我们使用两个指针 left 和 right 分别指向数组的开头和结尾。

原数组 nums 中的最大平方值可能位于两个指针所指向的元素中的较大值，则两者进行比对

如果left比right的大，则将left的数值放到result的末尾，否则就放right的数值，

并对应的将left向右移动一位或将right向左移动一位。

C++示例

class Solution {
  public:
  vector<int> sortedSquares(vector<int>& nums) {
    // 获取大小
    const int SIZE = nums.size();
    // 创建新的数组，并设置为同样的大小
    vector<int> result(SIZE);
    // 设置result的索引，从末尾开始
    int index = SIZE - 1;
    // 设置左右索引
    int left = 0, right = SIZE - 1;
    while(left <= right) {
      // 获取左右索引的数值，进行比对
      const int leftValue = nums[left] * nums[left];
      const int rightValue = nums[right] * nums[right];
      if (leftValue > rightValue) {
        // 左边数值大于右边，则将leftValue放到新数组的指定索引处,并向右偏移
        result[index] = leftValue;
        left++;
      }
      else {
        // 右边数值大于左边，则将rightValue放到新数组的指定索引处，并向左偏移
        result[index] = rightValue;
        right--;
      }
      index--;
    }
    return result;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

TypeScript示例

function sortedSquares(nums: number[]): number[] {
  let result: number[] = new Array(nums.length);
  let left = 0;
  let right = nums.length -1;
  let index = nums.length - 1;
  while (left <= right) {
    const leftValue = nums[left] * nums[left];
    const rightValue = nums[right] * nums[right];
    if (leftValue >= rightValue) {
      result[index] = leftValue;
      left++;
    } else {
      result[index] = rightValue;
      right--;
    }
    index--;
  }
  return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

待定…