Day1 有序数组平方-力扣977题

977. 有序数组的平方 - 力扣（LeetCode）

主要思路是双指针，写了三个版本，感觉优化后第三版更好。

版本一、平方后排序，时间复杂度O(n logn )

用的Arrays.sort排序

版本二、先平方，然后双指针比较大小，写入新数组

//未优化版
    public int[] sortedSquares(int[] nums) {
        //先遍历平方
        for (int i = 0; i < nums.length; i++) {
            nums[i] *= nums[i];
        }
        //数组其实是有序的， 只不过负数平方之后可能成为最大数了。
        //所以最大的数要么在左边，要么在右边，绝不会在中间
        int left = 0;
        int right = nums.length - 1;
        int index = nums.length - 1;
        //创建一个新数组，这样不会破坏原始数组的数据
        int []result = new int[nums.length];
        //left和right比较，大的就写在index位置，index--，left++，小的就写在index位置，index--，right--
        while (left <= right) {
            if (nums[left] > nums[right]) {
                result[index] = nums[left];
                left++;
            } else if (nums[left] < nums[right]){
                result[index] = nums[right];
                right--;
            }else{
                result[index] = nums[left];
                left++;
            }
            //if分支里面都要index--所以提取出来
            index--;

        }
        return result;
    }

版本三、平方和比较大小同时进行

    //优化版(合并平方计算到双指针遍历，简化if-else逻辑)
    public int[] sortedSquares(int[] nums) {
        //数组其实是有序的， 只不过负数平方之后可能成为最大数了。
        //所以最大的数要么在左边，要么在右边，绝不会在中间
        int left = 0;
        int right = nums.length - 1;
        int index = nums.length - 1;
        //创建一个新数组，这样不会破坏原始数组的数据
        int[] result = new int[nums.length];
        //left和right比较，大的就写在index位置，index--，left++，小的就写在index位置，index--，right--
        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            if (leftSquare > rightSquare) {
                result[index--] = leftSquare;
                left++;
            } else {
                result[index--] = rightSquare;
                right--;
            }
        }
        return result;
    }