Squares of a Sorted Array
你会得到一个按非递减顺序排列的整数数组 nums，其中可能包含负数。将每个值平方，并将平方后的结果作为一个新的数组返回，数组也要按非递减顺序排列。
函数
- numsinteger-array
- 已排序的整数数组，可以包含负数
- 返回值integer-array
- 每个值的平方，按非递减顺序排列
约束条件
1 ≤ nums.length ≤ 4000-104 ≤ nums[i] ≤ 104nums按非递减顺序排列。
示例
- 输入
- nums = [-6, -2, 1, 3, 7]
- 输出
- [1, 4, 9, 36, 49]
- 解释
- 原始顺序中的平方数是 36、4、1、9 和 49。负数 -6 和 -2 会得到较大的平方数，因此排序会把 36 移到靠近末尾的位置：
[1, 4, 9, 36, 49]。
- 输入
- nums = [-9, -4, -1]
- 输出
- [1, 16, 81]
- 解释
- 每个值都是负数，所以平方后的结果顺序相反：81、16、1 变成
[1, 16, 81]。
进阶
平方和排序需要 O(n log n)。你能用 O(n) 完成吗？
提示
逐个打开提示，每个都会多透露一点。
手动对
[-6, -2, 1, 3, 7]求平方。数组的哪一部分会失去顺序？为什么？最大的平方数总是来自
nums的第一个值或最后一个值，因为这两个值离 0 最远。在两端各放一个指针。比较两个平方数，把较大的那个写在结果的末尾，然后将对应的指针向内移动。重复这个过程，直到填满所有位置。
题解
平方运算会颠倒负数的顺序，因此平方后的数并未排序。不过，最大的平方数总是来自 nums 的两端之一。比较两端的数，将较大的平方数放在结果的末尾，然后向中间移动。
平方后排序
思路
用每个值的平方创建一个新数组，然后对它进行排序。排序会将平方值按顺序排列，无论它们原来的顺序如何。排序的时间复杂度为 O(n log n)，并且不考虑给定的顺序。
算法
- 为
nums中的每个x创建一个包含x * x的数组。 - 按数值升序排序并返回。
def sortedSquares(nums):
return sorted(x * x for x in nums)从两端开始的双指针
思路
一个数的平方会随着它与 0 的距离增大。在排序数组中，离 0 最远的值位于两端，最负的值在左边，最正的值在右边，所以最大的平方是 nums[left]² 或 nums[right]²。把较大的那个值写到结果数组的末尾，然后将对应的指针向内移动。指针之间剩下的部分仍然有序，所以每一步都适用同样的规律。
对于 [-6, -2, 1, 3, 7]：49 大于 36，因此放在最后。接着，36 大于 9，9 大于 4，4 大于 1，最后将 1 放在位置 0。每个值都只放置一次：时间复杂度为 O(n)，结果数组是唯一额外使用的数组。
算法
- 创建一个长度为
n的结果数组。将left设为 0，将right设为n-1。 - 让位置
pos从n-1递减到 0。 - 比较
nums[left]²和nums[right]²。 - 将较大的平方写入
pos，并将对应的指针向内移动一步。 - 返回结果。
def sortedSquares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
# the largest square left is always at one of the two ends
for pos in range(n - 1, -1, -1):
left_sq = nums[left] * nums[left]
right_sq = nums[right] * nums[right]
if left_sq > right_sq:
result[pos] = left_sq
left += 1
else:
result[pos] = right_sq
right -= 1
return result
易错点和边界情况
- 从结果数组的开头开始填入。最小的平方值出现在数值跨过 0 的位置，这个位置可能在中间；两端只能告诉你最大值。
- 比较
nums[left]和nums[right]，而不是比较它们的平方。-6 小于 3，但它的平方更大，所以[-6, 3]会得到[36, 9]。 - 当
left与right相遇时就停止。此时还有一个值没有放置；遍历每个位置，或者使用left <= right。 - 在 JavaScript 和 TypeScript 中，不带比较器的
sort()会把数字当作文本排序，因此[1, 4, 36, 9]会变成[1, 36, 4, 9]。传入(a, b) => a - b。
常见问题3
有序数组的平方的时间复杂度是多少？
双指针解法的运行时间为 O(n)：每个值只平方一次并放入结果中。平方后再排序的时间开销为 O(n log n)。两种方法都需要 O(n) 的内存来存储结果。
你能改成从前面填入结果吗？
可以，但你得先找到值从 0 的哪一侧跨到另一侧的位置，例如使用二分查找。然后，两个指针从该位置向外移动。从后往前填充可以避免查找，因为一开始就知道两端的位置。
“有序数组的平方”是一个归并问题吗？
是的。从右向左读取，负数的平方会组成一个有序列表，非负数的平方则会组成另一个有序列表。将它们合并就是归并排序中的合并步骤，因此只需线性遍历一次。
def sortedSquares(nums):
# 在这里编写代码测试 #1
测试 #2
参数
nums = [-6, -2, 1, 3, 7]
预期输出
[1, 4, 9, 36, 49]