有序数组的平方( LeetCode 977 )

本文内容为算法训练营一期内容，仅限训练营学员观看。

一、题目描述

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

二、题目解析

数组本身是有序的，对于一堆正数来说，平方之后顺序不会发生改变；而对于一堆负数来说，平方之后顺序发生了反转。

对于夹杂着正数和负数的数组来说，里面的负数平方之后有可能变成最大数。

所以，数组平方的最大值在数组的两端，不是最左边（负数）就是最右边（正数），不可能是中间的数字。

这样，我们设置两个索引，分别指向数组的两端，比如 left 指向起始位置，right 指向终止位置。

同时在设置一个新数组 result 用来存放最终的输出结果，让 index 指向 result 数组的终止位置。

• 如果 A[left] * A[left] < A[right] * A[right]，说明右边数的平方大于左边数的平方，那么 index 存放的数字是更大的那个数 A[right] * A[right]，并且将 right 向内移动，此时，index 已经放置好了正确的数字，将它向前移动，判断接下来应该放那个数字
• 如果 A[left] * A[left] >= A[right] * A[right]，说明左边数的平方大于右边数的平方，那么 index 存放的数字是更大的那个数 A[left] * A[left]，并且将 left 向内移动，此时，index 已经放置好了正确的数字，将它向前移动，判断接下来应该放那个数字
• 直到新数组 result 存放了所有的平方数

三、参考代码

1、Java 代码

class Solution {
    public int[] sortedSquares(int[] nums) {

        // 我们设置两个索引，分别指向数组的两端

        // right 指向终止位置
        int right = nums.length - 1;

        // left 指向起始位置
        int left = 0;

        // 设置一个新数组 result 用来存放最终的输出结果
        int[] result = new int[nums.length];

        // 让 index 指向 result 数组的终止位置，观察这个位置应该存放什么数字
        int index = result.length - 1;

        // left 向右移动，right 向左移动，当 left 大于 right 时，说明已经观察遍历了 nums 数组中的所有元素，跳出循环
        while (left <= right) {

            // 说明左边的平方数大于右边
            if (nums[left] * nums[left] > nums[right] * nums[right]) {

                // result 数组中 index 位置要存放更大的那个数，即 nums[left] * nums[left]
                result[index] = nums[left] * nums[left];

                // 由于相对较大的数是在 left 位置，上一行代码已经将它赋值到 index 位置
                // 所以此时 left 位置的数已经失去作用，将它向后移动
                left++;

                // 此时，index 位置已经存放好数，将它向前移动，观察下一个位置应该存放哪个数
                index--;

              // 说明右边的平方数大于左边
            } else {

                // result 数组中 index 位置要存放更大的那个数，即 nums[right] * nums[right]
                result[index] = nums[right] * nums[right];

                // 由于相对较大的数是在 right 位置，上一行代码已经将它赋值到 index 位置
                // 所以此时 right 位置的数已经失去作用，将它向前移动
                right--;

                // 此时，index 位置已经存放好数，将它向前移动，观察下一个位置应该存放哪个数
                index--;
            }
        }

        // 最后返回我们设置的结果数组即可
        return result;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com/582.html 
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有序数组的平方( LeetCode 977 ):https://leetcode-cn.com/problems/squares-of-a-sorted-array/
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        // 我们设置两个索引，分别指向数组的两端

        // right 指向终止位置
        int right = nums.size() - 1;

        // left 指向起始位置
        int left = 0;

        // 设置一个新数组 result 用来存放最终的输出结果
        vector<int> result = vector<int>(nums.size(), 0);

        // 让 index 指向 result 数组的终止位置，观察这个位置应该存放什么数字
        int index = result.size() - 1;

        // left 向右移动，right 向左移动，当 left 大于 right 时，说明已经观察遍历了 nums 数组中的所有元素，跳出循环
        while (left <= right) {

            // 说明左边的平方数大于右边
            if (nums[left] * nums[left] > nums[right] * nums[right]) {

                // result 数组中 index 位置要存放更大的那个数，即 nums[left] * nums[left]
                result[index] = nums[left] * nums[left];

                // 由于相对较大的数是在 left 位置，上一行代码已经将它赋值到 index 位置
                // 所以此时 left 位置的数已经失去作用，将它向后移动
                left++;

                // 此时，index 位置已经存放好数，将它向前移动，观察下一个位置应该存放哪个数
                index--;

              // 说明右边的平方数大于左边
            } else {

                // result 数组中 index 位置要存放更大的那个数，即 nums[right] * nums[right]
                result[index] = nums[right] * nums[right];

                // 由于相对较大的数是在 right 位置，上一行代码已经将它赋值到 index 位置
                // 所以此时 right 位置的数已经失去作用，将它向前移动
                right--;

                // 此时，index 位置已经存放好数，将它向前移动，观察下一个位置应该存放哪个数
                index--;
            }
        }

        // 最后返回我们设置的结果数组即可
        return result;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com/582.html 
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 有序数组的平方( LeetCode 977 ):https://leetcode-cn.com/problems/squares-of-a-sorted-array/
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # 我们设置两个索引，分别指向数组的两端

        # right 指向终止位置
        right = len(nums) - 1

        # left 指向起始位置
        left = 0

        # 设置一个新数组 result 用来存放最终的输出结果
        result = list(range(len(nums)))

        # 让 index 指向 result 数组的终止位置，观察这个位置应该存放什么数字
        index = len(nums) - 1

        # left 向右移动，right 向左移动，当 left 大于 right 时，说明已经观察遍历了 nums 数组中的所有元素，跳出循环
        while left <= right :

            # 说明左边的平方数大于右边
            if  nums[left] * nums[left] > nums[right] * nums[right] :

                # result 数组中 index 位置要存放更大的那个数，即 nums[left] * nums[left]
                result[index] = nums[left] * nums[left]

                # 由于相对较大的数是在 left 位置，上一行代码已经将它赋值到 index 位置
                # 所以此时 left 位置的数已经失去作用，将它向后移动
                left += 1

                # 此时，index 位置已经存放好数，将它向前移动，观察下一个位置应该存放哪个数
                index -= 1

              # 说明右边的平方数大于左边
            else :

                # result 数组中 index 位置要存放更大的那个数，即 nums[right] * nums[right]
                result[index] = nums[right] * nums[right]

                # 由于相对较大的数是在 right 位置，上一行代码已经将它赋值到 index 位置
                # 所以此时 right 位置的数已经失去作用，将它向前移动
                right -= 1

                # 此时，index 位置已经存放好数，将它向前移动，观察下一个位置应该存放哪个数
                index -= 1

        # 最后返回我们设置的结果数组即可
        return result

四、动画理解（没有声音）

程序员吴师兄算法训练营永久会员

打赏 收藏 海报 链接