algorithm - 数组的就地排列遵循此规则

Question

假设有一个数组，我们要查找奇数索引(索引从0开始)中的所有内容，并将其移动到末尾。偶数索引中的所有内容都将其移至开头。保留所有奇数索引项和所有偶数索引项的相对顺序。

即如果数组是

a1 b1 a2 b2 ...  an bn    

运行后变成

a1 a2 a3 ... an b1 b2 ... bn

这能否在 O(n) 时间内就地完成？

Answer 1

有可能，但是很复杂!更简单的 O(nlogn) 和 O(1) 空间解决方案可能更适合编码和缓存。

我们将解决与您不同的问题，但一旦我们解决了您的问题，您的问题就变得微不足道了。

考虑数组是

b1, a1, b2, a2, ..., bn, an

你必须把它转换成

a1, a2, ..., an, b1, b2, ..., bn

使用索引 1 到 2n，

我们看到这是由

i -> (n+1)*i (mod 2n+1).

---

一个 O(nlogn) 时间 O(1) 空间的解决方案

我们可以按如下方式使用分而治之。

首先对一些m接近n/2的转换

b1, a1, ..., bn, an

到

a1,a2,...am, b1,b2, ..bm, a(m+1), ..., an, b(m+1), ... , bn

通过递归地应用于前 2m 个元素，然后是剩余的元素。

现在我们需要做的就是将中间数组循环移动 m 个点(这可以在 O(n) 时间和 O(1) 空间内完成)

给予

a1, a2, .., am , a(m+1), ..., an, b1, b2, ..., bm, b(m+1), ..., bn.

当然，正如 IVlad 所指出的，这需要 O(logn) 堆栈空间。我们可以通过执行以下操作来解决这个问题:

我们有:

b1 a1, b2 a2, .. bm am, b(m+1) a(m+1), ..., bn an

现在交换数组后半部分的对给

b1 a1, b2 a2, .. bm am, a(m+1) b(m+1), ..., an bn

现在循环移位奇数位置的元素:b1, b2, .., bm, a(m+1), a(m+2) ..., a(n)。

这给出了类似的东西

a(m+1) a1, a(m+2) a2, ..., a(2m) am, a(2m+1) b(m+1),...,an b(n-m), b1 b(n-m+1),...,bm bn

现在再次交换数组的后半部分以给出

a(m+1) a1, a(m+2) a2, ..., a(2m) am, b(m+1) a(2m+1),...,b(n-m) an,b(n-m+1) b1,..., bn bm

现在递归求解第一部分和第二部分给

[a1 a2 ... am][a(m+1) ... a(2m)]   [a(2m+1) ...an b1 b2 .. bm][b(m+1) ... bn]

无论 2m >= n 与否，这都有效。

所以，这是 O(nlogn) 时间和 O(1) 空间算法。

---

O(n) 时间 O(1) 空间解决方案。

使用的思路与下面论文中使用的思路类似: A simple in-place algorithm for Inshuffle .

您需要阅读该论文才能理解以下内容。我建议你也阅读:How to master in-place array modification algorithms?

这基本上是上面论文中解决的问题的逆排列。

当 2n+1 是 3 = (3^m) 的幂时，就足以解决这个问题，因为我们可以在之后使用分而治之(就像 O(nlogn) 解决方案)。

现在 2n+1 和 n+1 互质，所以对 3^m 求模，我们看到 n+1 必须 是 2 的某个次方。(再次参阅该论文以了解原因: 基本上任何以 3^m 为模且与 3^m 互质的数都是 2 的幂，再次以 3^m 为模)。

假设 n+1 = 2^k(我们还不知道 k，请注意这是模 3^m)。

一种找出 k 的方法，计算 n+1 模 3^m 的幂，直到它变为 1。这给了我们 k(最多是 O(n) 时间)。

现在我们可以看到排列的循环(请参阅上面的论文/stackoverflow 链接了解它是什么)开始于

2^a*3^b

其中 0 <= a < k，且 0 <= b < m。

因此，您从每个可能的对 (a,b) 开始，然后遵循排列的循环，这给出了 O(n) 时间的就地算法，因为您接触每个元素的次数不超过常数次!

这有点简短(!)，如果您需要更多信息，请告诉我。