Leetcode 977. 有序数组的平方

977. 有序数组的平方

977. 有序数组的平方

• 标签：数组、双指针

• 难度：简单

描述：按非递减顺序排序的整数数组 nums

要求：返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。。

说明：

• 1 <= nums.length <= 10⁴

• -10^-4 <= nums[i] <= 10⁴

• 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]

思路

原数组 nums 实际上暗含一种顺序：绝对值大的数字在 nums 的两端，而不是在中间。使用 left 和 right 两个指针，left从左向右扫描，right从右向左扫描。每次比较 nums[left] 和 nums[right] 的平方，选择较大的值从右向左放入到 res 数组中。

public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int left, right, index;
        left = 0 ;
        right = index = n - 1;
        while (left <= right){
                if (nums[left] * nums[left] >= nums[right] * nums[right]){
                        res[index--] = nums[left] * nums[left];
                        left++;
                }else {
                        res[index--] = nums[right] * nums[right];
                        right--;
                }
        }
        return res;
}

977.有序数组的平方 题解