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] 为例。

首先初始化 left 和 right 指针，新建 res 数组，site 指针指向 res 数组的尾部。

# 初始化双指针
left = 0
right = len(nums) - 1
# 存储结果数组，从数组末尾开始存储
res = [-1] * len(nums)
site = len(nums) - 1

第 1 步，left = 0，right = 4，site = 4：

此时 nums[left] * nums[left] = 16 < nums[right] * nums[right] = 100，则 res[site] = nums[right] * nums[right] = 100，同时 right 向左移动一位，site 向左移动一位。

if nums[left] * nums[left] >= nums[right] * nums[right]:
    res[site] = nums[left] * nums[left]
    letf += 1
site -= 1

第 3 步，left = 1，right = 3，site = 2：

此时 nums[left] * nums[left] = 1 < nums[right] * nums[right] = 9，则 res[site] = nums[right] * nums[right] = 9，同时 right 向左移动一位，site 向左移动一位。

第 4 步，left = 1，right = 2，site = 1：

此时 nums[left] * nums[left] = 1 > nums[right] * nums[right] = 0，则 res[site] = nums[left] * nums[left] = 1，同时 left 向右移动一位，site 向左移动一位。

这里就要注意我在代码中特别强调的：

# 注意这里是 <=
while left <= right:

第 5 步，left = 2，right = 2，site = 0：

此时 nums[left] * nums[left] = 0 >= nums[right] * nums[right] = 0，则 res[site] = nums[left] * nums[left] = 0。

循环就此结束，输出结果 res。

本道题的解法，相当于遍历了一遍数组，时间复杂度为 O(n)。

因为额外维护了一个长度为 n 的 res 结果数组，所以空间复杂度也为 O(n)。

代码实现

Python 代码实现

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        if len(nums) == 1:
            return [nums[0] * nums[0]]
        # 初始化双指针
        left = 0
        right = len(nums) - 1
        # 存储结果数组，从数组末尾开始存储
        res = [-1] * len(nums)
        site = len(nums) - 1
        # 注意这里是 <=
        while left <= right:
            # 从两端遍历，将平方数组大得存储在 res 数组中
            if nums[left] * nums[left] < nums[right] * nums[right]:
                res[site] = nums[right] * nums[right]
                right -= 1
            else:
                res[site] = nums[left] * nums[left]
                left += 1
            site -= 1
        return res

Java 代码实现

class Solution {
    public int[] sortedSquares(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        int[] res = new int[nums.length];
        int index = res.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                res[index--] = nums[left] * nums[left];
                ++left;
            } else {
                res[index--] = nums[right] * nums[right];
                --right;
            }
        }
        return res;
    }
}

图解有序数组的平方到这就结束辣，数组实战第二题，讲解了双指针法的另外一种，学废了嘛？

更多精彩的好题我们后面不见不散，小婊贝们记得动动小手帮我点赞+在看呀~

我是帅蛋，我们下次见啦。