SortedSquare

题目：
we are given a sorted array of integers: [-3, -1, 0, 1, 2]. We want to generate a sorted array of their squares: [0, 1, 4, 9].

解题思路：
比较直白。首先做binary search找到绝对值最小的integer的index。然后从该index向两边扩张。

代码：

public class SortedSquare {
    public static int[] sortedSquare(int[] nums){
        if(nums == null || nums.length == 0){
            return nums;
        }
        int closestIndex = bSearch(nums);
        int[] rst = new int[nums.length];
        int left = closestIndex;
        int right = closestIndex + 1;
        int i = 0;
        while(left >= 0 && right <= nums.length - 1){
            if(Math.abs(nums[left]) <= Math.abs(nums[right])){
                rst[i] = (int) Math.pow(nums[left], 2);
                left--;
            }
            else{
                rst[i] = (int) Math.pow(nums[right], 2);
                right++;
            }
            i++;
        }
        while(left >= 0){
            rst[i] = (int) Math.pow(nums[left], 2);
            left--;
            i++;
        }
        while(right <= nums.length - 1){
            rst[i] = (int) Math.pow(nums[right], 2);
            right++;
            i++;
        }
        return rst;
    }
    private static int bSearch(int[] nums){
        int left = 0;
        int right = nums.length - 1;
        while(left + 1 < right){
            int mid = nums[(left + right) / 2];
            if(mid == 0){
                return (left + right) / 2;
            }
            else if(mid < 0){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        if(Math.abs(nums[left]) <= Math.abs(nums[right])){
            return left;
        }
        return right;
    }

    public static void main(String[] args){
        SortedSquare sortedSquare = new SortedSquare();
        int[] nums1 = {-3, -1, 0, 1, 4};
        int[] rst1 = sortedSquare.sortedSquare(nums1);
        int[] nums2 = {0, 1, 4};
        int[] rst2 = sortedSquare.sortedSquare(nums2);
        System.out.println(Arrays.toString(rst1));
        System.out.println(Arrays.toString(rst2));
    }
}