给定一个形如3n的数组
[x1, x2, x3... xn, y1, y2, y3... yn, z1, z2, z3... zn]
将它转换为[x1, y1, z1, x2, y2, z2, ... xn, yn, zn]
这里的xn, yn, zn可以是任何整数。请参见下面的示例输入和输出。
两个约束条件：
以下是一个示例输入和输出。
输入:
[5, 8, 11, 3, 2, 17, 21, 1, 9] 3n = 9。所以n = 3。
这里
x1=5 x2=8 x3=11 y1=3 y2=2 y3=17 z1=21 z2=1 z3=9
输出:
[5, 3, 21, 8, 2, 1, 11, 17, 9]
一种可能的O(n log n)解法： 只考虑x和y。现在我可以交换所有的y到它的位置，这会使我交换掉x2、x4、x6的位置。然后我会交换x2、x4，这会使x3、x7的位置不正确。下一次迭代将是x8、x16。这会让我达到O(n log n)，但不是O(n)。
本答案基于Peiyush Jain的工作（其参考文献非常不完整，但我没有时间梳理原地转置问题的历史）。请注意，3是25 = 5^2的一个原根，因为
>>> len(set(pow(3,n,25)for n in range(25)))
20
20是25的欧拉函数。根据数论中经典结果Jain定理1，3是所有5^k的原根。
当数组长度为3n时，位置k*n+j的元素的新位置是3*j+k。一般来说，除了最后一个元素外，i的新位置是(i*n)%(3*n-1)。请注意，n是3模3*n-1的乘法逆元，因此只有n是原根时，3才是原根。
Jain在这种情况下的观察是，如果3*n-1是5的幂，则上面的置换具有log_5(3*n-1)+1个不同的循环，由0到log_5(3*n-1)的5^k引导。(这基本上是原根的定义。)对于每个循环，我们只需要移动领导者，移动被领导者替代的元素，移动被替代元素替代的元素等，直到返回领导者。
对于其他数组大小，将数组分成O（log n）个隐式子数组，长度为3和5的幂加1，可被3整除：6、126、3126、78126等。进行一系列减小几何尺寸的旋转，使子数组连续，然后运行上述算法。由于David似乎不感兴趣将其写下来（显然他是有兴趣的，见另一个答案:），我将使用他的参考资料来得出一个包含3个分区的算法。
首先注意，如果我们可以使用算法A有效地解决一些m < n的问题，我们可以重新排列数组，以便我们可以应用A，然后留下一个较小的子问题。假设原始数组为
x1 .. xm x{m+1}.. xn y1 .. ym y{m+1} .. yn z1 .. zm z{m+1} .. zn
我们想要重新排列它
x1 .. xm y1 .. ym z1 .. zm x{m+1} .. xn y{m+1} .. yn z{m+1} .. zn
这基本上是将模式 AaBbCc 转换为 ABCabc，其中 A、B、C 和 a、b、c 分别具有相同的长度。我们可以通过一系列的反转来实现这一点。在此，用 X' 表示字符串 X 的反转：
AaBbCc
-> Aa(BbCc)' = Aac'C'b'B'
-> Aac'(C'b')'B' = Aac'bCB'
-> A(ac'bCB')' = ABC'b'ca'
-> ABCb'ca'
-> ABC(b'ca')' = ABCac'b
-> ABCa(c'b)' = ABCab'c
-> ABCabc
可能有更短的方法，但这仍然只是一定数量的操作，所以它只需要线性时间。在这里，可以使用更复杂的算法来实现一些循环移位，但那只是一种优化。
现在，我们可以递归地解决数组的两个分区，然后就完成了。
问题在于，什么样的m能让我们轻松地解决左边的部分呢？
为了弄清楚这一点，我们需要意识到我们想要实现的是一个特定的置换P，它作用于数组索引。每个置换都可以分解成一组循环a0 -> a1 -> ... -> a{k-1} -> a0，其中我们有P(ai) = a{(i + 1) % k}。处理这样的循环是很容易的，该算法在维基百科上有概述。
现在的问题是，在处理完一个循环后，要找到一个属于尚未处理的循环的元素。没有通用的解决方案，但对于一些特定排列，有描述不同循环的确切位置的好公式。
对于您的问题，只需选择m = (5^(2k) - 1)/3，使得m < n且k最大。所有不同循环的元素序列为5^0、5^1、...、5^{k-1}。您可以使用这些元素在数组左侧（移位后）上实现循环领导者算法，其时间复杂度为O(m)。
我们递归地解决剩余的右半部分，并获得解决问题的算法时间。
T(n) = O(m) + T(n - m)
由于 m >= Omega(n)，因此我们得到 T(n) = O(n)。
x,y,z改成a,b,c，那么通过谷歌搜索会惊奇地容易）。 - Bernhard Barker