977.有序数组的平方

题目描述

题解

系统自带排序法

先将数组中每个元素平方, 然后通过Arrays.sort() 方法排序

public int[] sortedSquares(int[] A) {
    for (int i = 0; i < A.length; i++) {
        A[i] = A[i] * A[i];
    }

    Arrays.sort(A);
    return A;
}

双指针

因为原数组已经排好序, 所以只需要比较收尾两个数的平方大小(因为左边可能是负数).

public int[] sortedSquares(int[] A) {
    int[] res = new int[A.length];
    for(int i = 0, j= A.length-1, pos = A.length-1;i <= j;){
        if(A[i]*A[i] > A[j]*A[j]){
            res[pos] = A[i] * A[i];
            i++;
        }else{
            res[pos] = A[j] * A[j];
            j--;
        }
        pos--;
    }
    return res;
}