[LeetCode] 977. Squares of a Sorted Array

[grandyang]

Given an integer array nums sorted in non-decreasing order, return  an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in non-decreasing order.

这道题给了一个非降序排列的数组，可以有负数存在，现在让求出每个数字的平方数，并且也是非降序排列。若数组中只有正数存在的话，则平方后的数组跟原数组的顺序还是相同的。但是负数的平方是正数，则顺序就会被打乱。最简单暴力的方法就是把平方数存入一个 TreeSet，利用其自动排序的功能可以得到所求的顺序了，注意这里需要用 multiset，因为可能存在重复值，参见代码如下：

解法一：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
		multiset<int> st;
		for (int num : A) st.insert(num * num);
		return vector<int>(st.begin(), st.end());
    }
};

当然若想进一步优化时间复杂度的话，可以使用双指针来做，用两个变量分别指向开头和结尾，然后比较，每次将绝对值较大的那个数的平方值先加入数组的末尾，然后依次往前更新，最后得到的就是所求的顺序，参见代码如下：

解法二：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int n = A.size(), i = 0, j = n - 1;
        vector<int> res(n);
        for (int k = n - 1; k >= 0; --k) {
            if (abs(A[i]) > abs(A[j])) {
                res[k] = A[i] * A[i];
                ++i;
            } else {
                res[k] = A[j] * A[j];
                --j;
            }
        }
        return res;
    }
};

Github 同步地址:

#977

类似题目：

Sort Transformed Array

Merge Sorted Array

参考资料：

https://leetcode.com/problems/squares-of-a-sorted-array/

https://leetcode.com/problems/squares-of-a-sorted-array/discuss/221922/Java-two-pointers-O(N)

https://leetcode.com/problems/squares-of-a-sorted-array/discuss/495394/C%2B%2B%3A-Simplest-one-pass-two-pointers

LeetCode All in One 题目讲解汇总(持续更新中...)