题号：1470
难度：Easy
链接：https://leetcode.cn/problems/shuffle-the-array

思路

常规解法不必多言，时间、空间复杂度都在 $O(n)$ 。

代码

#include <vector>

using std::vector;

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        //时间O(n)，空间O(n)
        vector<int> res(2*n);
        int i=0,j=n;
        for(int k=0;k<2*n;++k) res[k]=(k%2==0)?(nums[i++]):(nums[j++]);
        return res;
    }
};

进一步优化

时间来说显然优化到头了，可以在空间上做文章。

注意到，本体中元素的位置变化与其值无关，而与初始下标有关。

手动模拟几轮后可以发现如下规律：

1. 若初始下标 $i$ 满足 $i<n$ ，则其应当被移动到下标 $2*i$ 的位置。
2. 否则，应当被移动到下标 $\frac{(i-n)}{2} + 1$ 的位置。

那么，代码应当实现将元素逐个移动到其正确位置，在此过程中，仅需有限个变量暂时存储相关信息即可，所以空间复杂度在 $O(1)$ 水平。

在手动模拟中不难发现，在元素数目大于一定值时，无法在一轮连续交换后达成目的，那么就需要有某种标记说明当前位置元素是否已经在正确位置。并且，此标记不应当占用额外空间（否则其必与 $n$ 有关）。

有dalao提出两种方法，一是将已经在正确位置的元素标负；二是利用每个元素的二进制空闲位。

方法一无需说明。

方法二的巧妙之处在于，利用了题设给的数值范围。由于int型占用32bit空间，而题设给出的数值范围只利用了不到10bit，故剩下空闲的22bit可被利用，事实上只用其中10bit即可。

我们不直接将元素赋值给正确位置，而是将其存储在10-19位的10个bit中。最后，取数组每个元素的后0位bit即可。

方法一的代码

#include <vector>

using std::vector;

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        //时间O(n)，空间O(1)，以符号做标记
        if(n==1) return nums;
        nums[0] *= -1;
        nums[2*n-1] *= -1;
        int i=1;
        int p=i;
        while(i<2*n-1){
            if(nums[i]<0) p=++i;
            else{
                p=(p<n)?(2*p):((p-n)*2+1);
                int temp=nums[p];
                nums[p]=-nums[i];
                if(p!=i) nums[i]=temp;
            }
        }
        for(int &num:nums) num *= -1;
        return nums;
    }
};

方法二的代码

#include <vector>

using std::vector;

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        //时间O(n)，空间O(1)，利用空闲位做标记
        for(int i = 0; i < 2 * n; i ++){
            int j = i < n ? 2 * i : 2 * (i - n) + 1;
            nums[j] |= (nums[i] & 1023) << 10;
        }
        for(int& e: nums) e >>= 10;
        return nums;
    }
};

其中，&是按位与运算符，1023即10位连续1，(nums[i] & 1023)是取元素的前10个bit，再右移10位，使得前10位为0，之后10位为nums[i]中元素。将其与nums[j]做按位或运算（|），就实现了前10位存储原来的元素值，之后10位存储当前位置的正确值，再将其赋值给nums[j]。

这个过程不需要迭代跳转，按序顺次计算位置再赋值即可。最后取各元素的10-19位即求出解。

全文完