给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
1
2
3
4
| 输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
|
示例 2：
1
2
| 输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
|
提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums 已按 非递减顺序 排序
进阶：
暴力解法
求出所有数的平方，然后进行排序
1
2
3
4
5
6
7
8
9
| class Solution {
public int[] sortedSquares(int[] nums) {
for(int i = 0; i < nums.length; i++){
nums[i] = nums[i] * nums[i];
}
Arrays.sort(nums);
return nums;
}
}
|
时间复杂度：$O（n*log n）$
双指针法
i指向起始位置，j指向终止位置。
定义一个新数组ans，和A数组一样的大小，让k指向ans数组终止位置。
如果A[i] * A[i] < A[j] * A[j] ，那么ans[k–] = A[j] * A[j]; 。
如果A[i] * A[i] >= A[j] * A[j] ，那么ans[k–] = A[i] * A[i]; 。
因为平方后的最大元素都在头和尾
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length-1;
int[] ans = new int[nums.length];
int k = nums.length-1;
while(left <= right){
if(Math.abs(nums[left]) > Math.abs(nums[right])){
ans[k--] = nums[left] * nums[left];
left ++;
}else{
ans[k--] = nums[right] * nums[right];
right --;
}
}
return ans;
}
}
|
时间复杂度：$O(n)$