Powered By GitBook
977.Squares of a Sorted Array

977.Squares of Sorted Array

难度:Easy
给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。
1
示例 1:
2
3
输入:[-4,-1,0,3,10]
4
输出:[0,1,9,16,100]
5
示例 2:
6
7
输入:[-7,-3,2,3,11]
8
输出:[4,9,9,49,121]
9
10
11
提示:
12
13
1 <= A.length <= 10000
14
-10000 <= A[i] <= 10000
15
A 已按非递减顺序排序。
Copied!
代码如下:
1
class Solution {
2
public:
3
vector<int> sortedSquares(vector<int>& A) {
4
int k;
5
for(k=0;k<A.size();k++)
6
if(A[k]>0) break;
7
vector<int>a(A.begin(),A.begin()+k);
8
vector<int> b(A.begin()+k,A.end());
9
int al=a.size();
10
int bl=b.size();
11
int as=al-1,bs=0;
12
for(int i=0;i<al;i++)
13
a[i]*=a[i];
14
for(int i=0;i<bl;i++)
15
b[i]*=b[i];
16
//for(auto i:b) cout<<i<<endl;
17
// cout<<al<<bl<<endl;
18
if(!al) return b;
19
if(!bl) {
20
reverse(a.begin(),a.end());
21
return a;}
22
vector<int>res;
23
24
while(as>=0 && bs<bl)
25
{
26
a[as]<b[bs]? res.push_back(a[as--]):res.push_back(b[bs++]);
27
}
28
if(as >=0)
29
for(int i=as;i>=0;i--) res.push_back(a[i]);
30
if(bs<bl)
31
for(int i=bs;i<bl;i++) res.push_back(b[i]);
32
return res;
33
34
}
35
};
Copied!
1
执行用时 : 148 ms, 在Squares of a Sorted Array的C++提交中击败了19.29% 的用户
2
内存消耗 : 15.8 MB, 在Squares of a Sorted Array的C++提交中击败了100.00% 的用户
Copied!
Last modified 2yr ago
Copy link