leetcode 977 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 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]

思想

双指针法

最终结果从大到小对应 从两侧向中间，即最大值一定在数组左右两端

放两个指针 i,j分别于数组两端，比较 nums[i]平方与 nums[j]平方大小

较大的放于result最左侧，同时对应指针向内移动一位，直至 i=j(包含相等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] sortedSquares(int[] nums) {
        int i=0;
        int j=nums.length-1;
        int k=nums.length-1;
        int[] result = new int[nums.length];
        while(i<=j){
            if(nums[i]*nums[i]<=nums[j]*nums[j]){
                result[k]=nums[j]*nums[j];
                --j;
            }
            else{
                result[k]=nums[i]*nums[i];
                ++i;
            }
            --k;
        }
        return result;
    }

}