LeetCode 1470. 一维数组的重新洗牌（Shuffle the Array）

问题描述:

给定一个由2n个元素组成的数组nums: [x1,x2,…,xn,y1,y2,…,yn]。

请以[x1,y1,x2,y2,…,xn,yn]形式返回数组 。

注:

· 1 <= n <= 500；

· nums.length == 2n；

· 1 <= nums[i] <= 10^3；

示例:

C语言实现:

题目要求返回一个新数组，那么实现很简单：前n个元素重新分配到下标为偶数的位置；后n个元素重新分配到下标为奇数的位置；

代码如下：

如果要求直接修改数组，要有一个好的实现，有一点点难度。这里分享一个时间复杂度为O(n) 空间复杂度为O(1)的算法，如果有朋友有更好的解法，欢迎赐教。

首先我们注意到，无论如何，数组的首尾在洗牌前后都没有变，也就是不参与洗牌操作的。也就是只有下标1到2n-2的元素参与了洗牌。

接下来，我们用一个示例来说明，为了简便，元素和下标用相同的值。

（ 示例中每个带箭头的线表示元素移动操作，线上的数字表示当前操作是第几步。 ）首先，整个移动过程牵涉到下标的计算。

· 对于小于n的下标x，每次都会往每个元素前插入一个元素，所以新的下标将会是2x；

· 而对于大于等于n的下标y，新的下标将会是2(y-n)+1;

示例中n=3：

第1步，当前下标为1，新下标是2，备份2并将1移动到下标2；

第2步，对于下标2的元素，新下标是4，备份4并将备份的2移动到下标4；

第3步，对于下标4的元素，下标4大于n，新下标是3，备份3并将备份的4移动到下标3；

第4步，对于下标3的元素，下标3等于n，新下标是1，备份1并将备份的3移动到下标1，因为下标1已经洗过牌，所以结束；

我们发现似乎从第一个要洗牌的元素开始，按照它移动替换的顺序，用一个循环就能完成洗牌，但是有些例子要比这复杂一些，我们看下面的两个例子：

不同的箭头颜色表示需要的不同替换循环。我们发现有可能需要多个替换循环。

因此我们需要在替换循环之上再加一层循环来遍历1到n-1的元素（因为替换循环在n这个位置是左右对称的，所以不用遍历所有的1到2n-2元素），保证不会漏掉每一个替换循环。

这里有另外一个问题，如果某个下标已经被洗牌了，那么替换循环应该不处理，如何识别这种情况？我觉得比较简单而且不占空间的办法就是在洗牌的时候，将洗牌的元素转换成一个个特殊值，循环如果发现是特殊值，跳过。最后洗牌结束后，再将这些特殊值转换过来，这样会消耗O(n)的时间，但是总的时间复杂度依然是O(n)，因为内部的替换循环在这些情况下是被外层循环直接跳过的。这里因为题目说明所有的nums[i]都是大于1的，那么我们将可以将特殊值设置为相应的负数。

完整代码如下：

java语言实现:

Java 的实现和C语言的实现基本一致。

代码如下：

python语言实现:

Python 的实现和C语言的实现基本一致。

代码如下：