LeetCode 977. Squares of a Sorted Array

原题链接在这里：https://leetcode.com/problems/squares-of-a-sorted-array/

题目：

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

题解：

There could be negative number in A.

Thus have two pointer pointing to head and tail. Compare the squares and move the bigger pointer to the middle.

Time Complexity: O(n). n = A.length.

Space: O(1). regardless res.

AC Java:

class Solution {
    public int[] sortedSquares(int[] A) {
        if(A == null || A.length == 0){
            return A;
        }
        
        int [] res = new int[A.length];
        int i = 0;
        int j = A.length - 1;
        
        for(int po = A.length - 1; po>=0; po--){
            int si = A[i] * A[i];
            int sj = A[j] * A[j];
            if(si > sj){
                res[po] = si;
                i++;
            }else{
                res[po] = sj;
                j--;
            }
        }
        
        return res;
    }
}

类似Merge Sorted Array, Sort Transformed Array.