交织的数组三个相等大小的分区就地在O（n）时间 [英] Interleave three equally sized partitions in an array inplace in O(n) time
问题描述
鉴于形式的大小为3n的阵列
Given an array of size 3n of the form
[x1, x2, x3... xn, y1, y2, y3... yn, z1, z2, z3... zn]
转换为 [X1，Y1，Z1，X2，Y2，Z2，... XN，YN，锌]
下面XN，YN，锌可以是任意整数。见例如输入和输出以下
Here xn, yn, zn can be any integers. See example input and output below.
两个约束
- 请在O（N）
- O（1）内存（就地）
这是实施例的输入和输出如下所述。
An example input and output are as follows.
输入：
[5，8，11，3，2，17，21，1，9] 3N = 9，因此N = 3。
Input :
[5, 8, 11, 3, 2, 17, 21, 1, 9] 3n = 9. So n = 3.
下面
X1 = 5×2 = 8×3 = 11 Y1 = 3 Y2 = 2 Y3 = 17 Z1 = 21 Z2 = 1 Z3 = 9
输出：
[5,3，21，8，2，1，11，17，10]
一个可能为O（n log n）的溶液： 考虑到刚刚X的和y的。现在，我可以换全部的Y是它的位置，这将离我而去X2，X4，X6换出位置。然后，我会在X2掉，X4的这将离开X3，X7的失位。而下一次迭代是X8，X16的。这会带我去为O（n log n）的，但不是为O（n）。
One possible O(n log n) soln: Considering just x's and y's. Now I can swap all y's to its position which will leave me x2, x4, x6 swapped out of position. Then I will swap in x2, x4's which will leave x3, x7's out of position. And next iteration would be x8, x16's. This would take me to O(n log n) but not O(n).
推荐答案
由于大卫似乎并不感兴趣，把它写下来（好明显他的是的兴趣，看到对方的回答:)，我会使用他提到以算法与3个分区的情况下到达。
Since David does not seem interested in writing it down (well obviously he is interested, see the other answer :), I will use his reference to arrive at an algorithm for the case with 3 partitions.
首先要注意，如果我们能够有效地解决这个问题的一些的 M＆LT; ñ的使用算法的 A 的，我们可以重新排列数组，这样我们就可以应用的 A 的，并随后留下一个较小的子问题。说原来阵列
First note that if we can solve the problem efficiently for some m < n using an algorithm A, we can rearrange the array so that we can apply A and are then left with a smaller subproblem. Say the original array is
x1 .. xm x{m+1}.. xn y1 .. ym y{m+1} .. yn z1 .. zm z{m+1} .. zn
我们希望将它重新排列，以
We want to rearrange it to
x1 .. xm y1 .. ym z1 .. zm x{m+1} .. xn y{m+1} .. yn z{m+1} .. zn
这是基本的模式 AABBCC 到 ABCABC A变换，其中A，B，C和A，B ，C具有相同的长度，分别为。我们能够做到这一点通过一系列的逆转。设X'表示字符串X的逆转这里：
This is basically a transformation of the pattern AaBbCc to ABCabc where A, B, C and a, b, c have the same lengths, respectively. We can achieve that through a series of reversals. Let X' denote the reversal of string X here:
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
有可能是一个更短的方式，但是这仍然是操作只是一个恒定数，所以只需要线性时间。人们可以使用更复杂的算法在这里实现一些循环移位，但是这只是一种优化。
There's probably a shorter way, but this is still just a constant number of operations, so it takes only linear time. One could use a more sophisticated algorithm here to implement some of the cyclic shifts, but that's just an optimization.
现在，我们可以解决我们的数组的两个分区递归，我们就大功告成了。
Now we can solve the two partitions of our array recursively and we're done.
现在的问题是，这将是一个不错的米，使我们能够轻松解决的左半部分？
The question remains, what would be a nice m that allows us to solve the left part easily?
要弄清楚这一点，我们需要认识到，我们要实现的是一个特定的置换 P中的数组索引。每个排列可以分解成一组的循环 A0 - ＆GT ; A1 - ＆GT; ... - ＆GT;一个{K-1} - ＆GT; A0 ，为此，我们有P（AI）=一{（I + 1）％K}。这是很容易处理这样一个周期中就地，算法概述<一href="http://en.wikipedia.org/wiki/In-place_matrix_transposition#Non-square_matrices%3a_Following_the_cycles"在维基百科相对=nofollow>。
To figure this out, we need to realize that what we want to implement is a particular permutation P of the array indices. Every permutation can be decomposed into a set of cycles a0 -> a1 -> ... -> a{k-1} -> a0, for which we have P(ai) = a{(i + 1) % k}. It is easy to process such a cycle in-place, the algorithm is outlined on Wikipedia.
现在的问题是，你处理完一个周期，发现那是你还没有处理的周期的一部分的元素之后。没有此没有通用的解决方案，但对于某些特定的排列有很好的公式描述究竟的位置是属于不同周期的一部分。
Now the problem is that after you completed processing one of the cycle, to find an element that is part of a cycle you have not yet processed. There is no generic solution for this, but for some particular permutations there are nice formulas that describe what exactly the positions are that are part of the different cycles.
有关问题，你只要选择M =（5 ^（2K） - 1）/ 3，使得M＆LT; n和k是最大的。这是所有不同的周期的一部分的元素的序列是5 ^ 0,5 ^ 1，...，5 ^ {K-1}。可以使用的那些来实现在O（米）在阵列的左侧部分到周期的首领算法（移位后）。
For your problems, you just choose m = (5^(2k) - 1)/3, such that m < n and k is maximum. A sequence of elements that are part of all the different cycles is 5^0, 5^1, ..., 5^{k-1}. You can use those to implement the cycle-leader algorithm on the left part of the array (after the shifting) in O(m).
我们解决剩余的右半部分递归，并得到一个算法，及时解决问题。
We solve the leftover right part recursively and get an algorithm to solve the problem in time
T(n) = O(m) + T(n - m)
和因为m> =欧米茄（N），我们得到T（N）=为O（n）。
and since m >= Omega(n), we get T(n) = O(n).
这篇关于交织的数组三个相等大小的分区就地在O（n）时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
