面试测试 - 重新排列阵列

Question

可能重复:
重新排序数组元素

在给定的元素数组中,如[a1,a2,a3,.. an,b1,b2,b3,.. bn,c1,c2,c3,... cn]编写程序将它们合并为[a1,b1, C1,A2,B2,C2,...一,BN,CN].我们必须在O(1)额外空间中进行.

样品测试用例:

Input #00:

{1,2,3,4,5,6,7,8,9,10,11,12}

Output #00:

{1,5,9,2,6,10,3,7,11,4,8,12}

Explanation:

Here as you can notice, the array is of the form
{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4} 

编辑:我在亚马逊布局测试中得到它.已经尝试了很长时间了.PLease提供伪代码.我尝试的是为第二个元素e找到新的位置p(第一个已经在正确的位置),在p处插入e并对位置p处的旧元素重复相同的操作.但这是在一个周期结束.我尝试检测循环并将起始位置递增1.但即使这样也行不通.

EDIT2:

#include <iostream>
using namespace std;

int pos(int i, int n) 
{
    if(i<n)  
     {
         return  3*i;

           }

       else if(i>=n && i<2*n)
       {

            return 3*(i-n) + 1;
            }
    else if(i>=2*n && i<3*n)
       {
            return 3*(i-2*n) + 2;
            }
return -1;
}
void printn(int* A, int n)
{
         for(int i=0;i<3*n;i++)  
             cout << A[i]<<";";

    cout << endl;
     }

void merge(int A[], int n)
{
 int j=1;    
 int k =-1;
 int oldAj = A[1];
 int count = 0;
 int temp;
 while(count<3*n-1){

 printn(A,n);
 k = pos(j,n);
 temp = A[k];
 A[k] = oldAj;
 oldAj = temp;
 j = k;
 count++;
 if(j==1) {j++;}
}

 }

int main()
{
    int A[21] = {1,4,7,10,13,16,19,2,5,8,11,14,17,20,3,6,9,12,15,18,21};
    merge(A,7);

    cin.get();}

Answer 1

这就是所谓的就地in-shuffle算法,如果你想有效地完成它,这是一项非常艰巨的任务.我只是发布这个条目,所以人们不发布他们所谓的"解决方案"声称它可以扩展到O(1)空间,没有任何证据......

下面列出了一个简单案例的文章a1 a2 a3 ... an b1 b2 b3 .. bn:

http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf

Answer 2

这是像您这样的问题的一般解决方案。

首先，对于每个源索引，您都知道目标索引。现在，你就这样：

1. 采取第一项。找到它的最终位置。记住该位置的项目，并将第一个项目存储在那里。现在，找到所记忆的项目所属的位置，并将该项目放在那里，记住被替换的项目。继续这个过程，直到到达第一个项目的位置（显然）。
2. 如果您已更换了所有物品，则您已完成。如果没有，则取出第一个未转移的项目，并从该项目开始继续重复步骤 1 的过程。

您需要标记已转移的项目。有不同的方法可以做到这一点：例如，您可以使用项目存储中的一位。

好的，上面的解决方案并不完全是 O(1)，因为它需要N额外的位。以下是按位置划分的 O(1) 解决方案的概要，但效率较低：

考虑项目 a1、b1、c1。它们需要位于结果的前 3 个位置。因此，我们正在执行以下操作：记住 a1、b1、c1，将除这三项之外的数组压缩到后面（因此看起来像这样： , , , a2, a3, ..., an, b2, b3, .. ., bn, c2, c3, ..., cn)，并将项目 a1, b1, c1 放在开头的位置。现在，我们找到了前 3 项的位置，因此对 a2、b2、c2 等继续此过程。

编辑：
让我们考虑一下上面概述的时间复杂度。表示列表大小3*n。我们需要n步骤。列表的每一次压缩都可以一次完成，因此 是O(n)。步骤中的所有其他操作都是O(1)，因此我们得到了完全的n * O(n) = O(n^2)复杂性。然而，这远不是最好的解决方案，正如 @yi_H 提到的，线性时间解决方案需要大量使用或多或少的高级数学。