有序数组的平方

有序数组的平方

此题目使用快慢指针法，一个指针指向数组开头，一个指针指向数组末尾。

因为是有序数组，最大值不是在左边，就是在右边，不会在中间。

使用快慢指针，可以得出

如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j];

如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] sortedSquares(int[] nums) {
        if(nums.length == 1){
            nums[0] = nums[0]*nums[0];
            return nums;
        }

        int i=0;
        int j = nums.length-1;
        int k=nums.length-1;
        int[] res = new int[nums.length];
        while(k >= 0){
            if(nums[i]*nums[i] < nums[j]*nums[j]){
                res[k--] = nums[j]*nums[j];
                j--;
            }
            if(nums[i]*nums[i] >= nums[j]*nums[j] ){
                res[k--] = nums[i]*nums[i];
                i++;
            }
        }    

        return res;

    }
}