<分区>
Possible Duplicate:
Reordering of array elements
在给定的元素数组中，如 [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] 编写一个程序来合并它们，如 [a1 ,b1,c1,a2,b2,c2,...an,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}
编辑: 我在亚马逊分类考试中得到了它。已经尝试了很长时间了。 请提供伪代码。我尝试的是为第二个元素 e(第一个已经在正确的位置)找到新位置 p，在 p 处插入 e 并对位置 p 处的旧元素重复相同的操作。但这是一个循环结束。 我尝试检测周期并将起始位置递增 1。但即使这样也不起作用。
编辑2:
#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();}