原题地址（中等）

方法1—sort

思路

直接用sort函数就好了

代码

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        for(int i = 0; i < A.size(); i++) 
            A[i] *= A[i];
        sort(A.begin(), A.end());
        return A;
    }
};

时空复杂度

时间复杂度O(logN) 空间复杂度O(1)

方法2—双指针

思路

方法一中没有利用原数组有序这个条件

可以分为三种情况：

• 原数组全负，逆序排列就好了
• 原数组全正，按原顺序排列就好了
• 原数组先正后负，找出前半段负数和后半段正数，这两部分都有序，对着两部分用双指针合并成一个数组就好了。

代码

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int n = A.size();
        if(n == 0)  return {};
        vector<int> ans;
        if(A[0] >= 0){
            for(auto a : A) 
                ans.push_back(a * a);
        }
        else if(A[n-1] <= 0) {
            for(int i = n-1; i >= 0; i--)
                ans.push_back(A[i] * A[i]);
        }
        else{
            int reg = 0;
            for(int i = 0; i < n; i++){
                if(A[i] >= 0){
                    reg = i-1;
                    break;
                }
            }
            int p = reg, q = reg+1;
            while(p >= 0 && q < n) {
                if(A[p]*A[p] <= A[q] * A[q]){
                    ans.push_back(A[p]*A[p]);
                    p--;
                }
                else{
                    ans.push_back(A[q]*A[q]);
                    q++;
                }
            }
            while(p >= 0){
                ans.push_back(A[p]*A[p]);
                p--;
            }
            while(q < n) {
                ans.push_back(A[q]*A[q]);
                q++;
            }
        }
        return ans;
    }
};

时空复杂度

时间复杂度O(N)
空间复杂度O(1)