题目描述

给定一个整数数组 A，以非降序排列，返回每个数字都经过平方后的数组，也以非降序排列。

样例

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

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

注意

• 1 <= A.length <= 10000
• -10000 <= A[i] <= 10000
• A 是非降序排列的。

算法1

(直接排序) $O(n \log n)$

• 将 A 中的每个数字平方后，直接 sort 排序。

时间复杂度

• 遍历一次数组，然后排序，时间复杂度为 $O(n \log n)$。

空间复杂度：

• 仅需要常数的空间。

C++ 代码

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        for (auto &x : A)
            x = x * x;
        sort(A.begin(), A.end());
        return A;
    }
};

算法2

(归并) $O(n)$

1. 原数组其实是以数字 0 作为分界，前半部分在平方后是倒序的，后半部分是正序的。
2. 所以我们可以根据这一性质，另开一个数组，然后做两个有序数组的 merge。

时间复杂度

• 每个数字仅遍历常数次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的数组存储结果。

C++ 代码

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int n = A.size(), mid = n;
        for (int i = 0; i < n; i++) {
            if (A[i] >= 0) {
                mid = i;
                break;
            }
            else
                A[i] = -A[i];
        }
        vector<int> B;
        int i = mid - 1, j = mid;
        while (i >= 0 || j < n) {
            if (i < 0)
                B.push_back(A[j++]);
            else if (j == n)
                B.push_back(A[i--]);
            else {
                if (A[i] < A[j])
                    B.push_back(A[i--]);
                else
                    B.push_back(A[j++]);
            }
        }
        for (auto &x : B)
            x = x * x;
        return B;
    }
};