【LeetCode】977. 有序数组的平方

in programming •  4 months ago 

1 题目描述

977. 有序数组的平方要求给定一个按非递减顺序排列的整数数组 nums,返回一个新的数组,其中每个元素都是原数组中对应元素的平方,并且新数组也需要是非递减顺序排列的。

2 解题思路

这个问题的关键在于原数组中的负数和正数部分。对于非负数来说,它们的平方会保持原有的顺序;而对于负数来说,由于平方后会变成正数,所以可能会改变原有的顺序。因此,我们可以考虑使用双指针法来解决这个问题。

  • 初始化两个指针 leftright 分别指向数组的起始位置和末尾位置。
  • 使用第三个指针 k 指向新数组的末尾。
  • 比较 nums[left]nums[right] 平方后的大小:
    • 如果 nums[left] * nums[left] 大于 nums[right] * nums[right],则将 nums[left] 的平方放入新数组的末尾,并将 left 向右移动一位;
    • 否则,将 nums[right] 的平方放入新数组的末尾,并将 right 向左移动一位。
  • 重复上述步骤直到 leftright 指针相遇或交错。

这种方法能够确保数组中的元素按照非递减顺序排列,因为每次都是选择较大的平方值放到新数组的末尾,这样就避免了对整个数组进行额外的排序操作。

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 指针指向数组的结尾。
  • 原地修改:虽然本题允许创建一个新的数组来存储结果,但双指针技术可以高效地完成任务。
  • 从后往前填充:新数组从后往前填充,以确保最后得到的数组是非递减排序的。
Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!