LC 1470. 重新排列数组，通过一道简单题，熟悉下int类型的高低位位运算操作。

题目

1470. 重新排列数组

https://leetcode.cn/problems/shuffle-the-array/

给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,…,xn,y1,y2,…,yn] 的格式排列。

请你将数组按 [x1,y1,x2,y2,…,xn,yn] 格式重新排列，返回重排后的数组。

简单模拟

思路

这个过程没有复杂设计，我们开辟一个ans结果数组，然后双指针插入新值，2*i表示xi，2*i+1则表示yi的插入位置。

代码

1
2
3
4
5
6
7
8

public int[] shuffle(int[] nums, int n) {
    int[] ans = new int[2 * n];
    for (int i = 0; i < n; i++) {
        ans[2 * i] = nums[i];
        ans[2 * i + 1] = nums[i + n];
    }
    return ans;
}

复杂度

时间

整个过程遍历一次数组，时间复杂度O(n)。

空间

按我们一般理解的结果空间不算在额外的空间开销内，空间复杂度O(1)。

但实际上，相对nums入参数组，我们还是开辟了一个额外的空间，为了方便与下面的解法对比，我们认为这里空间复杂度O(n)。

位运算

思路

上面解法在一道简单题面前其实已经足够了。

之所以写这篇题解，是因为想借着这道题熟悉下位运算操作int高低位。

我们可以在nums原数组上就地操作，这样理论上的空间开销更小。

题干规定了 nums[i]<=1000 >=1 ，因此使用低十位存原数值，高十位存新值，最后统一用高位替换低位。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public int[] shuffle(int[] nums, int n) {
    for (int i = 0; i < 2 * n; i++) {
        // j表示当前nums[i]对应新下标
        int j = i < n ? 2 * i : 2 * (i - n) + 1;
        // 在j的高位存储nums[i]，低位存储原值
        nums[j] |= ((nums[i] & 1023) << 10);
    }
    // 使用高位替换低位
    for (int i = 0; i < 2 * n; i++) {
        nums[i] >>= 10;
    }
    return nums;
}

位运算知识点：

  • nums[i] & 1023 取当前值的低10位；
  • (nums[i] & 1023) << 10 将低10位的值放到高10位；
  • nums[j] |= ((nums[i] & 1023) << 10) 将nums[i]低10位的值放到nums[j]的高10位，同时保留nums[j]的低10位；

复杂度

时间

遍历两次数组，时间复杂度O(n)。

空间

就地操作数组，使用int高低位同时存储新旧值，空间复杂度O(1)。

可以看到相比解法1这里空间效率更高。

Ref