有序数组的平方
需求
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
1
2
3
4
2
3
4
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
1
2
2
思路一
采用双指针遍历，因为是有序的数组，原数组前面的负数如果平方后比它最后一位数平方更大，那肯定是新数组中最大的了，所以直接丢到往新数组的尾部，如果小于最后一位则将原数组的最后一位平方后丢入新数组，以此类推，自然最后就剩下小的在前面了。
代码
public int[] sortedSquares(int[] nums) {
//定义左右指针
int l=0,r=nums.length-1;
int[] result=new int[nums.length];
//新数组从尾部开始添加元素
int index=nums.length-1;
while(l<=r){
//如果原数组的负数比最后一位大则将原数组的第一位放入新数组尾部
if(nums[l]*nums[l]>nums[r]*nums[r]){
result[index--]=nums[l]*nums[l];
l++;//添加完自增移动指针
}else{
//否则原封不动将原数组最后一位添加到新数组尾部
result[index--]=nums[r]*nums[r];
r--;//添加完自减移动指针
}
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
思路二
暴力排序，也就是先平方后排序，时间和空间复杂度都会增加
代码
public int[] sortedSquares(int[] nums) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
ans[i] = nums[i] * nums[i];
}
Arrays.sort(ans);
return ans;
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
上次更新: 2023/12/29 11:32:56