1 题目描述
977. 有序数组的平方要求给定一个按非递减顺序排列的整数数组 nums
,返回一个新的数组,其中每个元素都是原数组中对应元素的平方,并且新数组也需要是非递减顺序排列的。
2 解题思路
这个问题的关键在于原数组中的负数和正数部分。对于非负数来说,它们的平方会保持原有的顺序;而对于负数来说,由于平方后会变成正数,所以可能会改变原有的顺序。因此,我们可以考虑使用双指针法来解决这个问题。
- 初始化两个指针
left
和right
分别指向数组的起始位置和末尾位置。 - 使用第三个指针
k
指向新数组的末尾。 - 比较
nums[left]
和nums[right]
平方后的大小:- 如果
nums[left] * nums[left]
大于nums[right] * nums[right]
,则将nums[left]
的平方放入新数组的末尾,并将left
向右移动一位; - 否则,将
nums[right]
的平方放入新数组的末尾,并将right
向左移动一位。
- 如果
- 重复上述步骤直到
left
和right
指针相遇或交错。
这种方法能够确保数组中的元素按照非递减顺序排列,因为每次都是选择较大的平方值放到新数组的末尾,这样就避免了对整个数组进行额外的排序操作。
3 Java 代码实现
1public class Solution {
2 public int[] sortedSquares(int[] nums) {
3 int[] ans = new int[nums.length];
4 int left = 0;
5 int right = nums.length - 1;
6 int k = nums.length - 1; // // 新数组的右指针
7 while (left <= right) {
8 if (nums[left] * nums[left] > nums[right] * nums[right]) {
9 ans[k--] = nums[left] * nums[left];
10 left++;
11 } else {
12 ans[k--] = nums[right] * nums[right];
13 right--;
14 }
15 }
16 return ans;
17 }
18}
4 注意事项
- 双指针:使用双指针技术,其中
left
指针指向数组的开头,而right
指针指向数组的结尾。 - 原地修改:虽然本题允许创建一个新的数组来存储结果,但双指针技术可以高效地完成任务。
- 从后往前填充:新数组从后往前填充,以确保最后得到的数组是非递减排序的。