LeetCode刷题（177）～有序数组的平方【双指针】

题目描述

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

示例 1：

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

  

 

  
1
  
2
 

示例 2：

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

  

 

  
1
  
2
 

提示：

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

解答 By 海轰

提交代码

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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

运行结果

提交代码（双指针）

vector<int> sortedSquares(vector<int>& A) { int n=A.size(); vector<int> ans(n); int i=0;// 非负数的第一个数字 while(i<n&&A[i]<0) ++i; int j=i-1;// 最大的负数 int t=0; while(i<n&&j>=0) { if(A[i]*A[i]<A[j]*A[j]) { ans[t++]=A[i]*A[i]; ++i; } else { ans[t++]=A[j]*A[j]; --j; } } while(i<n) { ans[t++]=A[i]*A[i]; ++i; } while(j>=0) { ans[t++]=A[j]*A[j]; --j; } return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108780833