LeetCode 有序数组的平方 [简单]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array

示例 1：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例 2：

输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

题目分析

解法1

先把数据平方，然后再排序 依赖于排序算法的时间和空间复杂度 O(nlogn)

解法2

双指针，从两边进行缩进 直到完成 指定长度数组的填充 时间复杂度 O(1)空间复杂度 O(n)

代码实现

public class LeetCode_33_SortedSquares {

    public static void main(String[] args) {
        int[] numsA = {-4, -1, 0, 3, 10};
        int[] numsB = {-4, -1, 0, 3, 10};
        int[] res = sortedSquares(numsA);
        int[] res2 = sortedSquares2(numsB);
        System.out.println(Arrays.toString(res));
        System.out.println(Arrays.toString(res2));
    }

    public static int[] sortedSquares2(int[] A) {
        if (A == null) {
            return null;
        }
        if (A.length == 0) {
            return new int[]{};
        }
        int[] B = new int[A.length];
        int left = 0;
        int right = A.length - 1;
        int index = A.length - 1;
        while (index >= 0) {
            if (A[left] < 0 && -A[left] > A[right]) {
                B[index--] = A[left] * A[left++];
            } else {
                B[index--] = A[right] * A[right--];
            }
        }
        return B;
    }

    public static int[] sortedSquares(int[] A) {
        if (A == null) {
            return null;
        }
        if (A.length == 0) {
            return new int[]{};
        }
        for (int i = 0; i < A.length; i++) {
            A[i] = A[i] * A[i];
        }
        Arrays.sort(A);
        return A;
    }
}