977. Squares of a Sorted Array

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation