📃 题目描述

题目链接：977. 有序数组的平方 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

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

🔔 解题思路

最简单的办法，遍历数组挨个平方后做排序，遍历的时间复杂度是 O(N)，排序的时间复杂度就是 O(LogN) ，即这种暴力法的时间复杂度是 O(LogN)，空间复杂度是 O(1)

还有一种时间复杂度 O(N) ，空间复杂度 O(N) 的方法：

由于数组中存在负数，负数平方之后可能比正数的平方要大。但是，数组的排序是有序的，也就是说，数组平方的最大值一定在数组的两端，不是最左边就是最右边，不可能是中间。

考虑用左右指针。左指针指向第一个元素，右指针指向最后一个元素。

这样，我们可以保证，随着左右指针的不断往中间靠拢，它们代表的平方数也越来越小。所以，我们只需要新建一个数组 res 用来存储最终的结果集，每次将左右指针比较出来的较大的结果从数组末端插入数组即可：

• 如果 nums[left]^2 > nums[right]^2 => nums[left]l^2 加入 res 结果集，并 left ++;
• 如果 nums[right]^2 >= nums[left]^2 => nums[right]l^2 加入 res 结果集，并 right --;

class Solution {
    public int[] sortedSquares(int[] nums) {
        if (nums == null || nums.length == 0) {
            return nums;
        }

        int[] res = new int[nums.length];
        // res 数组的下标
        int index = nums.length - 1;

        int left = 0;
        int right = nums.length - 1;
        
        // 注意这里是 left <= right, 因为最后要处理最后一个元素
        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;
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(N)