博客

977. 有序数组的平方

题目描述

给你一个按

非递减顺序

排序的整数数组 nums，返回

每个数字的平方

组成的新数组，要求也按

非递减顺序

排序。

思路分析

以官方的方法二思路为例，双指针。

描述中提到了

非递减顺序

的数组，也就是说，刚开始的数组已经排好顺序了，我们只要利用到这个前提，就可以很轻松的解答它。

什么是

非递减顺序

的数组呢？比如：

• -2 -1 0 1 1 5
• -5 -4 -2 -1
• 0 2 9 5 5 6

这些都是

非递减顺序

的数组，它们里面重复的数字出现，顺序是递增的或者是前一个与后一个相等的。负数在平方后会变成正数，也就是说，如果负数数组是递增的，那么他平方后的正数数组一定是递减的。

以 [-2,-1,0,1,1,5 ]这个数组为例，我们以第一个非负整数0为边界，可以分成[-2,-1]和[0,1,1,5]两个数组，平别平方后变成了[4,1]和[0,1,1,25]两个数组。

这个时候我们定义left为（初始数字是）负整数数组的最大下标，定义right为（初始数字是）非负整数数组的初始下标0，每次比较两个下标对应的数字，谁小就把谁放到最终的结果（新建一个数组）中。如果放入了左边的数，那么将左边的数字指针左移；如果放入了右边的数，那么将右边的数字指针右移。

如果left小于0了或者right超出范围了，那么退出循环。将多余数组中的数组按照从小到大的顺序放入结果中。

代码

 public int[] sortedSquares(int[] nums) {
        // 先把数字平方，放到一个新数组中
        int[] newNums = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            newNums[i] = nums[i] * nums[i];
        }

        int resultNum = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                resultNum = i;
                break;
            }
            if (i == nums.length-1) {
                resultNum = i;
            }
        }

        int nonNegativeIntegerIndex = resultNum;
        // （初始数字）负整数集合
        int[] negativeIntegerNums = Arrays.copyOfRange(newNums, 0, nonNegativeIntegerIndex);
        // （初始数字）非负整数集合
        int[] nonNegativeIntegerNums = Arrays.copyOfRange(newNums, nonNegativeIntegerIndex, newNums.length);

        int left = negativeIntegerNums.length - 1;
        int right = 0;

        int[] result = new int[newNums.length];
        int index = 0;
        
        while (right <= nonNegativeIntegerNums.length - 1 && left >= 0) {
            int leftNum = negativeIntegerNums[left];
            int rightNum = nonNegativeIntegerNums[right];
            if (leftNum < rightNum) {
                result[index] = leftNum;
                index++;
                left--;
            } else {
                result[index] = rightNum;
                index++;
                right++;
            }
        }

        while (left >= 0) {
            int leftNum = negativeIntegerNums[left];

            result[index] = leftNum;
            index++;
            left--;
        }

        while (right <= nonNegativeIntegerNums.length - 1) {
            int rightNum = nonNegativeIntegerNums[right];

            result[index] = rightNum;
            index++;
            right++;
        }
        return result;
    }

结果