977.Squares of a Sorted Array

977.Squares of Sorted Array

难度:Easy

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

示例 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) {
        int k;
        for(k=0;k<A.size();k++)
            if(A[k]>0) break;
        vector<int>a(A.begin(),A.begin()+k);
        vector<int> b(A.begin()+k,A.end());
        int al=a.size();
        int bl=b.size();
        int as=al-1,bs=0;
        for(int i=0;i<al;i++)
            a[i]*=a[i];
        for(int i=0;i<bl;i++)
            b[i]*=b[i];
        //for(auto i:b) cout<<i<<endl;
       // cout<<al<<bl<<endl;
        if(!al) return b;
        if(!bl) { 
            reverse(a.begin(),a.end());
            return a;}
        vector<int>res;

        while(as>=0 && bs<bl)
        {
            a[as]<b[bs]? res.push_back(a[as--]):res.push_back(b[bs++]);
        }
        if(as >=0)
            for(int i=as;i>=0;i--) res.push_back(a[i]);
        if(bs<bl)
            for(int i=bs;i<bl;i++) res.push_back(b[i]);
        return res;

    }
};
执行用时 : 148 ms, 在Squares of a Sorted Array的C++提交中击败了19.29% 的用户
内存消耗 : 15.8 MB, 在Squares of a Sorted Array的C++提交中击败了100.00% 的用户

Last updated