我必须交错给定的表单数组
{a1,a2,....,an,b1,b2,...,bn}
如
{a1,b1,a2,b2,a3,b3}
在 O(n) 时间和 O(1) 空间中。
例：
Input - {1,2,3,4,5,6}
Output- {1,4,2,5,3,6}
这是按索引排列的元素：
Initial Index Final Index
0 0
1 2
2 4
3 1
4 3
5 5
通过观察后举了一些例子，我发现ai (i<n/2) goes from index (i) to index (2i)&bi (i>=n/2) goes from index (i) to index (((i-n/2)*2)+1)。您可以自己验证这一点。如果我错了，请纠正我。
但是，我无法在代码中正确应用此逻辑。
我的伪代码：
for (i = 0 ; i < n ; i++)
if(i < n/2)
swap(arr[i],arr[2*i]);
else
swap(arr[i],arr[((i-n/2)*2)+1]);
它不起作用。
如何编写算法来解决此问题？
元素bn已经处于正确的位置，所以让我们忘记它，只担心其他N = 2n-1元素。 请注意，N 总是奇数。
现在问题可以重述为"将每个位置的元素移动到位置2i % Ni
" 位置0 处的项目不会移动，因此让我们从位置 1 开始。
如果从位置 1 开始并将其移动到位置 2%N，则必须记住位置 2%N 的项目，然后再更换它。 位置 2%N 的那个转到位置 4%N，4%N 的那个转到 8%N，依此类推，直到您回到位置 1，在那里您可以将剩余的物品放入您离开的插槽中。
您保证返回插槽 1，因为 N 是奇数，乘以 2 mod 奇数是可逆的。 但是，在回来之前，您不能保证覆盖所有职位。 整个排列将分解为一定数量的循环。
如果你可以在每个周期的一个元素上开始这个过程，那么你将完成整个工作。 麻烦的是弄清楚哪些已经完成，哪些没有完成，所以你不会重复任何周期。
我认为你不能以符合你的时间和空间限制的方式对任意 N 做到这一点...... 但是，如果 N = 2 x-1 对于某个x，那么这个问题就容易得多，因为每个周期都恰好包含某个位模式的循环移位。 您可以在每个索引的恒定时间内为每个周期生成单个代表(称为周期领导者)。 (我将在最后的附录中描述该过程)
现在，我们有了满足约束条件的递归算法的基础。
给定[a1...an,b1...bn]：
找到最大的x，使得 2x<= 2n
旋转中间元素以创建
[a1...ax,b1...bx,ax+1...an,bx+1...bn]使用上述过程以线性时间交错数组的第一部分，因为它的模数为 2x-1
递归以交错数组的最后一部分。
由于我们递归的数组的最后一部分保证最多是原始数组的一半大小，因此对于时间复杂度，我们有这种递归：
T(N) = O(N) + T(N/2)
= O(N)
请注意，递归是一个尾部调用，因此您可以在常量空间中执行此操作。
附录：为班次 mod 2x-1生成循环领导者
弗雷德里克森和凯斯勒在一篇名为"生成 2 种颜色珠子项链的算法"的论文中给出了一个简单的算法。 您可以在此处获取 PDF：https://core.ac.uk/download/pdf/82148295.pdf
实施很容易。 从 x 0 开始，并重复：
- 将最低顺序 0 位设置为 1。 让这个有点y
- 从顶部开始复制低阶位
- 结果是，如果 x-y 除以 x
- 重复直到所有 x 1
例如，如果 x=8 并且我们在10011111，则最低的 0 是位 5。 我们将其切换到 1，然后从顶部复制其余部分以给出10110110. 不过，8-5=3,3 不除以 8，所以这个不是循环领先者，我们继续下一个。
我要提出的算法可能不是o(n)。 它不是基于交换元素，而是基于移动元素，如果你有一个列表而不是数组，这可能是 O(1)。
给定 2N 个元素，在每次迭代 (i) 中，您将元素置于位置 N/2 + i 并将其移动到位置 2*i
a1,a2,a3,...,an,b1,b2,b3,...,bn
| |
a1,b1,a2,a3,...,an,b2,b3,...,bn
| |
a1,b1,a2,b2,a3,...,an,b3,...,bn
| |
a1,b1,a2,b2,a3,b3,...,an,...,bn
等等。
N = 4 的示例
1,2,3,4,5,6,7,8
1,5,2,3,4,6,7,8
1,5,2,6,3,4,7,8
1,5,2,6,3,7,4,8
一个有点复杂的想法是假设每个位置都有以下值：
1, 3, 5, ..., 2n-1 | 2, 4, 6, ..., 2n
a1,a2, ..., an | b1, b2, ..., bn
然后使用本文中解释的两个排序数组的内联合并O(n)时间O(1)空间复杂性。但是，我们需要在此过程中管理此索引。
这个问题中描述了一个实用的线性时间*就地算法。包括伪代码和 C 代码。
它涉及将前 1/2 的项目交换到正确的位置，然后解密移动的 1/4 项目的排列，然后对剩余的 1/2 数组重复。
解开排列的混乱利用了这样一个事实，即左侧项目以交替的"添加到末尾，交换最旧"模式移动到右侧。我们可以在这个排列中找到第 i 个索引，这个规则是这样的：
即使对于 i，结尾在 i/2.
对于奇数 i，最旧的在步骤 (i-1)/2 处添加到末尾
*数据移动次数肯定是O(N)。该问题询问解密索引计算的时间复杂度。我相信它并不比O(lg lg N)差。