在O(n)时间内在阵列中交错三个大小相等的分区

Question

给出一个大小为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可以是任何整数.请参阅下面的示例输入和输出.

两个约束

1. 做O(n)
2. O(1)内存(inplace)

输入和输出的示例如下.

输入:
[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)soln: 仅考虑x和y.现在我可以将所有y换成它的位置,这将使我x2,x4,x6换出位置.然后我将交换x2,x4,这将使x3,x7离开位置.下一次迭代将是x8,x16.这将花费我O(n log n)而不是O(n).

Answer 1

由于 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其中ABCabcA、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)。