英文原文
Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn].
Return the array in the form [x1,y1,x2,y2,...,xn,yn].
Example 1:
Input: nums = [2,5,1,3,4,7], n = 3 Output: [2,3,5,4,1,7] Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].
Example 2:
Input: nums = [1,2,3,4,4,3,2,1], n = 4 Output: [1,4,2,3,3,2,4,1]
Example 3:
Input: nums = [1,1,2,2], n = 2 Output: [1,2,1,2]
Constraints:
1 <= n <= 500nums.length == 2n1 <= nums[i] <= 10^3
中文题目
给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。
示例 1：
输入：nums = [2,5,1,3,4,7], n = 3 输出：[2,3,5,4,1,7] 解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]
示例 2：
输入：nums = [1,2,3,4,4,3,2,1], n = 4 输出：[1,4,2,3,3,2,4,1]
示例 3：
输入：nums = [1,1,2,2], n = 2 输出：[1,2,1,2]
提示：
1 <= n <= 500nums.length == 2n1 <= nums[i] <= 10^3
通过代码
高赞题解
这个问题空间复杂度是 O(n) 的解法太简单了，不多说了。说说空间复杂度为 O(1) 的做法，原地完成：）
实际上，有两个思路可以完成这一点。
以下解析可能结合代码看会更好理解。
思路一
因为题目限制了每一个元素 nums[i] 最大只有可能是 1000，这就意味着每一个元素只占据了 10 个 bit。（2^10 - 1 = 1023 > 1000）
而一个 int 有 32 个 bit，所以我们还可以使用剩下的 22 个 bit 做存储。实际上，每个 int，我们再借 10 个 bit 用就好了。
因此，在下面的代码中，每一个 nums[i] 的最低的十个 bit（0-9 位），我们用来存储原来 nums[i] 的数字；再往前的十个 bit（10-19 位），我们用来存储重新排列后正确的数字是什么。
在循环中，我们每次首先计算 nums[i] 对应的重新排列后的索引 j，之后，取 nums[i] 的低 10 位（nums[i] & 1023），即 nums[i] 的原始信息，把他放到 nums[j] 的高十位上。
最后，每个元素都取高 10 位的信息(e >> 10)，即是答案。
我的参考代码（C++）：
class Solution {
public:
vector<int> shuffle(vector<int>& nums, int n) {
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;
}
};思路二
利用题目中限制每一个元素 nums[i] 都大于 0。我们可以使用负数做标记。
标记什么？标记当前 nums[i] 存储的数字，是不是重新排列后的正确数字。如果是，存负数；如果不是，存正数（即原本的数字，还需处理）。
我们每次处理一个 nums[i]，计算这个 nums[i] 应该放置的正确位置 j。但是，nums[j] 还没有排列好，所以我们暂时把 nums[j] 放到 nums[i] 的位置上来，并且记录上，此时 nums[i] 的元素本来的索引是 j。现在，我们就可以安心地把 nums[i] 放到 j 的位置了。同时，因为这已经是 nums[i] 正确的位置，取负数，即标记这个位置已经存放了正确的元素。
之后，我们继续处理当前的 nums[i]，注意，此时这个新的 nums[i]，本来的索引是 j。所以我们根据 j 算出它应该存放的位置，然后把这个位置的元素放到 nums[i] 中，取负做标记。
这个过程以此类推。这就是代码中 while 循环做的事情。
直到 nums[i] 的值也是负数，说明 i 的位置也已经是重新排列后的正确元素了，我们就可以看下一个位置了。
在 for 循环中，如果某一个元素已经是小于零了，说明这个位置已经是正确元素了，可以忽略。
这个算法虽然有两重循环，但是时间复杂度是 O(n) 的，因为每个元素最多会被重新排列一次，然后会被最外面的 for 循环访问一次。一旦重新排列过，for 的访问只是一次 if 判断而已。
当然，最后，数组中的所有元素还需要从负数转换回正数。
我的参考代码（C++）：
class Solution {
public:
vector<int> shuffle(vector<int>& nums, int n) {
for(int i = 0; i < 2 * n; i ++)
if(nums[i] > 0){
// j 描述当前的 nums[i] 对应的索引，初始为 i
int j = i;
while(nums[i] > 0){
// 计算 j 索引的元素，也就是现在的 nums[i]，应该放置的索引
j = j < n ? 2 * j : 2 * (j - n) + 1;
// 把 nums[i] 放置到 j 的位置，
// 同时，把 nums[j] 放到 i 的位置，在下一轮循环继续处理
swap(nums[i], nums[j]);
// 使用负号标记上，现在 j 位置存储的元素已经是正确的元素了
nums[j] = -nums[j];
}
}
for(int& e: nums) e = -e;
return nums;
}
};觉得有帮助请点赞哇！
## 统计信息
| 通过次数 | 提交次数 | AC比率 |
| :------: | :------: | :------: |
| 54672 | 64899 | 84.2% |
## 提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
| :------: | :------: | :------: | :--------: | :--------: |
