977. 有序数组的平方

977. 有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/description/

方法一：

一个包含正负数的非递减数组，等同于一个从正负数分割线开始的两个有序正负数组

对于两个有序数组的合并，可以利用类似归并排序的思想，为两个数组的最小位置各自分配一个指针

分别向左和右移动，选择当前较小的平方值存入新数组：

public class Solution {
    public int[] sortedSquares(int[] nums) {
        // 类似归并排序，从中间到两边发散
        int[] arr =  new int[nums.length];
        int mid = -1;
        for(int i = 0; i < nums.length; ++ i){
            if(nums[i] >= 0){
                mid = i;
                break;
            }
        }
        int l = -1, r = -1;
        int idx = 0;
        if(mid != -1 && nums[mid] == 0){
            arr[idx] = 0;
            ++idx;
            l = mid - 1;
            r = mid + 1;
        }else if(mid != -1 && mid != 0){
            l = mid - 1;
            r = mid;
        }else if(mid == 0){
            // 全是正数
            r = 0;
        }
        else{
            // mid = -1, 全是负数
            l = nums.length - 1;
            r = nums.length;
        }

        while(r < nums.length && l >= 0 && idx < nums.length){
            int rsq = nums[r]* nums[r];
            int lsq = nums[l]* nums[l];
            if(lsq > rsq){
                arr[idx] = rsq;
                ++r;
            }else{
                arr[idx] = lsq;
                --l;
            }
            ++idx;
        }
        while(l >= 0){
            arr[idx++] =  nums[l] * nums[l];
            --l;
        }
        while(r < nums.length){
            arr[idx++] = nums[r] * nums[r];
            ++r;
        }
        return arr;
    }
}

方法二：

根据数组特性，这是一个凹下去的数组，类似一元二次函数。

只需要在左右边界最高点的地方分配两根指针，逐渐向中心移动。

每次移动前选择其中较大的一方，以倒序的方式存入新数组中：

public class Solution2 {
    public int[] sortedSquares(int[] nums) {
        // 从两边到中间收拢
        int[] arr = new int[nums.length];
        int idx = nums.length - 1;
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int lsq = nums[l] * nums[l];
            int rsq = nums[r] * nums[r];
            if(lsq > rsq){
                arr[idx] = lsq;
                ++l;
            }else{
                arr[idx] = rsq;
                --r;
            }
            --idx;
        }
        return arr;
    }
}