题目
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100]
示例 2:
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
思路
由于数组是有序的,平方之后可能变换顺序的只有负数的情况,最大的数一定出现在两边,用双指针,指向两边,新建一个数组,比较两端的元素,从大到小补充新数组迭代元素,直到补充完成。
实现
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] newNums = new int[nums.length];
int l = 0;
int r = nums.length - 1;
while(l <= r){
int a = nums[l]*nums[l];
int b = nums[r]*nums[r];
if(a > b){
newNums[--n] = a;
l++;
}else{
newNums[--n] = b;
r--;
}
}
return newNums;
}
}