给定一个按非递减顺序排序的整数数组 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% 的用户