Keshawn_lu's Blog

Leetcode 977. 有序数组的平方

字数统计: 232阅读时长: 1 min
2020/10/16 Share

题目简介:

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

示例 1:

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

示例 2:

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

提示:

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

思路:

双指针,每次将绝对值大的那一个数字的平方放至答案数组的最后面即可(即逆序放置)。

时间复杂度O(n)

代码如下:

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
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {

int left = 0;
int right = A.size() - 1;

vector<int> res(A.size());
int pos = A.size() - 1;

while(left <= right){

if(abs(A[left]) > abs(A[right])){

res[pos] = A[left] * A[left];
pos--;
left++;
}
else{

res[pos] = A[right] * A[right];
pos--;
right--;
}
}

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: