leetcode 977. 有序数组的平方(Squares of a Sorted Array)

佚名 6年前 (2019-04-08) 随笔 1018人围观抢沙发百度已收录

题目描述：

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

示例 1：

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

示例 2：

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

提示：

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。

解法：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        vector<int> res;
        int l = 0, r = 0;
        int sz = A.size();
        while(l < sz && A[l] < 0){
            l++;
        }
        if(l == 0){
            // all positive
            for(int val : A){
                res.push_back(val*val);
            }
        }else if(l == sz){
            // all negative
            for(int i = sz-1; i >= 0; i--){
                res.push_back(A[i]*A[i]);
            }
        }else{
            r = l;
            l--;
            while(l >= 0 && r < sz){
                if(A[l] + A[r] >= 0){
                    res.push_back(A[l]*A[l]);
                    l--;
                }else{
                    res.push_back(A[r]*A[r]);
                    r++;
                }
            }
            while(l >= 0){
                res.push_back(A[l]*A[l]);
                l--;
            }
            while(r < sz){
                res.push_back(A[r]*A[r]);
                r++;
            }
        }
        return res;
        
    }
};