977.有序数组的平方

难度：简单

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 10^4
• (-10)^4 <= nums[i] <= 10^4
• nums 已按 非递减顺序 排序

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

解题思路

暴力做法自然是平方后再排序或者是排序后再平方，但这样的算法时间复杂度显然是超过 O(n) 的。

以空间换时间，如果不采用原地算法，代码逻辑上会不会更简单呢？答案是肯定的。

考虑题目中，数组 nums 已按非递减顺序排序 这个条件。显然，如果数组 nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。

这样一来，如果我们能够找到数组 nums 中负数与非负数的分界线，那么就可以用类似 归并排序 的方法了。

归并排序是一类不同的排序方法。“归并”的含义是将两个或者两个以上的有序表组合成一个新的有序表。利用归并的思想容易实现排序，且这种实现方法已为读者熟悉，无论是顺序存储结构还是链表存储结构，都可以在 O(m+n) 的时间量级上实现。

归并排序是一个基于分治法思想的算法，拿两个已经有序的序列重新组合成一个有序的序列。

我的思路：

1. 遍历一遍数组，找到旧数组中负数与非负数的分界线下标 boundary，他指向旧数组中平方后值最小的元素
2. 此时可以确定新数组中第一个元素的值 nums[boundary]，并且该分界线左侧的元素是平方后往左边递增的，右侧的元素是平方后往右边递增的
3. 等于说我们已经获得了两个有序的数组，以及新数组的起始元素，此时可以开始使用 归并排序
4. 使用两个指针 left、right 一开始都指向位置 boundary，之后 left 往左走，right 往右走，每次比较两个指针指向的元素平方后的值，选择较小的那个放入新数组，并移动对应的指针
5. 当某一方向的指针移至边界时，将另一指针还未遍历到的元素平方后依次放入新数组

我的代码

public int[] sortedSquares(int[] nums) {
    int boundary = 0;
    // 找到最后一个非正数的位置
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] < 0) {
            boundary = i;
        } else {
            break;
        }
    }
    int left = boundary;
    int right = boundary + 1;
    int[] result = new int[nums.length];
    int i;
    // 合并两个有序数组
    for (i = 0; left >= 0 && right < nums.length; i++) {
        if (nums[left] * nums[left] < nums[right] * nums[right]) {
            result[i] = nums[left] * nums[left];
            left--;
        } else {
            result[i] = nums[right] * nums[right];
            right++;
        }
    }
    // 处理剩余的非正数部分
    while (left >= 0) {
        result[i++] = nums[left] * nums[left];
        left--;
    }
    // 处理剩余的非负数部分
    while (right < nums.length) {
        result[i++] = nums[right] * nums[right];
        right++;
    }
    return result;
}

时间复杂度：O(n)

空间复杂度：O(n)，因为不是一个原地算法

其中 if (nums[left] * nums[left] < nums[right] * nums[right]) 这一句可以改为 if (-nums[left] < nums[right])，因为此时的 left 要么是负数，要么是最小的非负数，这样写的好处是可以避免 数值溢出 的问题。

更优思路

上述算法中，在使用归并排序的时候，我们想着先找到最小的元素，再从小到大一点一点填充新数组。

那么反过来，能不能先找到最大的元素，再从大到小来填充新数组呢？答案是可以的。

而且由于原数组已经是 非递减顺序，所以数组两端的元素平方值将是最大的。因此，可以直接从数组的两端开始比较平方值，无需先寻找分界点。

而且这样做，当 left 和 right 相遇的时候，新数组刚好走到了首位元素的位置。

那么我们就不必一开始去寻找边界值，也不必再最后去处理某一指针移动至边界的情况，代码变得更加直观和高效。

更优代码

public int[] sortedSquares(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    int[] result = new int[nums.length];
    for (int i = nums.length - 1; left <= right; i--) {
        if (-nums[left] > nums[right]) {
            result[i] = nums[left] * nums[left];
            left++;
        } else {
            result[i] = nums[right] * nums[right];
            right--;
        }
    }
    return result;
}

时间复杂度：O(n)

空间复杂度：O(n)，因为不是一个原地算法

其中 if (nums[left] * nums[left] > nums[right] * nums[right]) 这一句改为了 if (-nums[left] > nums[right])，因为此时的 left 要么为负数，要么为最小的非负数，所以这样写可以避免 数据溢出 的问题。

总结

八大排序真应该好好看看，感觉好多题目，虽然不会直接套用，但是其中的思想往往值得借鉴。

逆向思维也需要培养，有时候反过来思考问题，会有意想不到的好效果。