在 O(n) 时间和 O(1) 空间中交错数组 {a1,a2,....,an,b1,b2,...,bn} 到 {a1,b1,a2,b2,a3,b3}

Question

我必须交错给定的表单数组

{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]);

它不起作用。

如何编写算法来解决这个问题？

Answer 1

我要提出的算法可能不是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