Leetcode 209 的 'inplace' 解法

今天刷题时遇到了一个很有趣的题解,分享出来。

题目的链接是 977. 有序数组的平方,难度为 Easy。

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

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4

题目本身很简单,大致有两种解题方法:

最简单的是平方后排序,时间复杂度O(nlogn):

public int[] sortedSquares(int[] nums) {
    for (int i = 0; i < nums.length; ++i) {
        nums[i] = nums[i] * nums[i];
    }
    Arrays.sort(nums);
    return nums;
}

另外一种解法是双指针法,空间复杂度 O(n),时间复杂度 O(n):

public int[] sortedSquares(int[] nums) {
    final int len = nums.length;
    final int[] result = new int[len];
    for (int i = 0; i<len; ++i) {
        nums[i] *= nums[i];
    }
    int lo = 0;
    int hi = len - 1;
    int j = hi;
    while (lo <= hi) {
        if (nums[lo] > nums[hi]) {
            result[j--] = nums[lo];
            ++lo;
        } else {
            result[j--] = nums[hi];
            --hi;
        } 
    }
    return result;
}

就地解法

那问题来了,这道题有没有就地解法呢?也就是空间复杂度 O(1),时间复杂度 O(n)。

答案是有的。

在使用双指针法时,该题的就地解法设计难点在于:填充数组时,左指针的数据可能会覆盖还未确定位置的右侧数据,因而必须额外新建一个数组。

不过仔细观察题目给的数据范围为 -10^4 <= nums[i] <= 10^4。因为 10^4 = 0b10011100010000,也就是说在取绝对值的情况下,测试数据最多占用 14 个比特位,而输入的 int 类型为 32 比特。因此,我们完全可以利用原数组项中前 16 个空闲比特位来存储交换后的值,实现 inplace 解法。用 java 实现如下:

public int[] sortedSquares(int[] nums) {
    final int len = nums.length;

    // 数组取绝对值
    for (int i = 0; i < len; ++i) {
        if (nums[i] < 0) nums[i] *= -1;
        else break;
    }

    int lo = 0;
    int hi = len - 1;
    int j = hi;
    while (lo <= hi) {
        // (1)
        if ((nums[lo] & 0xFFFF) > (nums[hi] & 0xFFFF)) {
            // (2)
            nums[j--] |= (nums[lo] & 0xFFFF) << 16;
            lo++;
        } else {
            nums[j--] |= (nums[hi] & 0xFFFF) << 16;
            hi--;
        }
    }

    for (int i = 0; i < len; ++i) {
        nums[i] >>= 16;
        nums[i] *= nums[i];
    }

    return nums;

}

注意事项:

  1. 注意优先级,(1) 处的括号不能省略;

  2. 注意对于 (2) 处的写法,通过编译生成字节码可以发现,Java编译器会先把 j-- 存储为一个变量 t,然后再计算 nums[t] |= ...。即:

    // 原语句:
    nums[j--] |= (nums[lo] & 0xFFFF) << 16;
    
    // 编译后的等价语句,其中 var5 对应于 j:
    var10001 = var5--;
    nums[var10001] |= (nums[lo] & '\uffff') << 16;