【实战】ACM 选手图解 LeetCode 有序数组的平方

大家好呀，我是你们的帅蛋。

今天解决有序数组的平方，同样是使用双指针法的经典题。

不同于【LeetCode27 移除元素】的快慢指针，这次的双指针是一种另外的用法。咱话不多说，直接开整。

LeetCode 977：有序数组的平方

题意

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

示例

输入：nums = [-4,-1,0,3,10]

输出：[0,1,9,16,100]

解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

提示

• 1 <= len(nums) <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 已按非递减顺序排序

题目解析

水题，难度简单。

现在我还没讲到排序，如果小婊贝们知道快排，这道题最无脑暴力的方法其实就是每个元素平方完了，再快排一下。

这个过程就涉及到两步：

• 第 1 步：一层 for 循环遍历数组，将各元素平方后存入数组，这一步的时间复杂度为 O(n)。
• 第 2 步：快排，时间复杂度为 O(nlogn)。

总的时间复杂度显然是 O(n + nlogn)，这个复杂度说实话稍微有点高了。

我们要善于使用题意来选择最合适的办法。

数组 nums 是非递减排序的数组，那就相当于是个递增的数组，且每个元素的取值 -10^4 <= nums[i] <= 10^4，这就证明元素值有正有负。

通过这两个条件其实我们可以得出，平方以后的最大值肯定出现在两侧，不是左边就是右边（负数的平方为正数）。

碰到这种情况，我们一般祭出双指针法来解决，left 指向下标 0，right 指向下标 n - 1：

• 新建一个结果数组 res 存储最后的结果，site 指向数组末尾，数组从后向前存储。
• 若 nums[left] * nums[left] < nums[right] * nums[right]，res[site] = nums[right] * nums[right]。
• 若 nums[left] * nums[left] >= nums[right] * nums[right]，res[site] = nums[left] * nums[left]。

图解

以 nums = [-4,-1,0,3,10] 为例。

首先初始化