「每日LeetCode」2020年10月16日

本文最后更新于：2023年3月19日 晚上

Lt977. 有序数组的平方、双指针

977. 有序数组的平方

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
示例 1：

1
2
输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例 2：

1
2
输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A 已按非递减顺序排序。

思路

暴力排序

直接对平方后的数组进行排序得到结果

双指针

使用双指针可以在得到平方和的同时就得到有序的结果序列，减少一次排序过程

解答

暴力排序

1
2
3
4
5
6
7
/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortedSquares = function (A) {
  return A.map((e) => e ** 2).sort((a, b) => Number(a) - Number(b));
};

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortedSquares = function (A) {
  const res = [];
  let left = 0,
    right = A.length - 1,
    index = A.length - 1;
  while (left <= right) {
    if (A[left] ** 2 >= A[right] ** 2) {
      res[index--] = A[left++] ** 2;
    } else {
      res[index--] = A[right--] ** 2;
    }
  }
  return res;
};