面试测试 - 重新排列数组 [英] Interview test - rearrange the array
问题描述
可能重复：
数组元素的重新排序
在类似的元件的给定阵列〔A1，A2，A3，...的，B1，B2，B3，... BN，C1，C2，C3，... CN]撰写程序合并它们像〔A1 ，B1，C1，A2，B2，C2，...的，BN，CN]。 我们必须这样做，在O（1）额外的空间。
样品测试案例：
输入＃00：
{1,2,3,4,5,6,7,8,9,10,11,12}
输出＃00：
{1,5,9,2,6,10,3,7,11,4,8,12}
说明：
在这里，你可以看到，该阵列的形式为
{A1，A2，A3，A4，B1，B2，B3，B4，C1，C2，C3，C4}
编辑： 我在亚马逊分班考试得到了它。一直在尝试了很长的时间。 请提供伪code。我试图寻找新的位置P的第二个元素E（1日已经在正确的位置），在P插入e和重复相同的旧元素的位置p。但是，这是结束一个周期。 我试图检测周期，并以1递增起始位置但是，即使这是行不通的。
EDIT2：
的#include＆LT;的iostream＆GT;
使用名字空间std;
INT POS（INT I，INT N）
{
如果（ⅰn种）
{
返回3 *我;
}
否则如果（ⅰ＆GT; = N＆安培;＆安培;我2 * n）的
{
返回3 *（i-n型）+ 1;
}
否则如果（ⅰ＆GT; = 2 * N＆安培;＆安培;我3; * n）的
{
返回3 *第（i-2 * N）+ 2;
}
返回-1;
}
无效printn（INT * A，INT N）
{
的for（int i = 0;我3; * N;我++）
COUT＆LT;＆LT; A [1] - ;＆LT;;;
COUT＆LT;＆LT; ENDL;
}
无效合并（INT A []，INT N）
{
INT J = 1;
INT K = -1;
INT oldAj = A [1];
诠释计数= 0;
INT温度;
而（计数3; * N-1）{
printn（A，N）;
K = POS（J，N）;
TEMP = A [K];
A [K] = oldAj;
oldAj =温度;
J = K表;
算上++;
如果（j == 1）{J ++;}
}
}
诠释的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};
合并（A，7）;
cin.get（）;}
这是所谓就地在洗牌的算法，这是一个非常艰巨的任务，如果你想有效地做到这一点。我只是张贴此项这样的人不张贴他们所谓的解决方案，声称它可以延长O（1）空间工作，没有任何证据......
下面是一份文件，一个简单的情况下，当列表的形式为： A1 A2 A3 ...的B1，B2，B3 ...... BN ：
<一个href="http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf">http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf
Possible Duplicate:
Reordering of array elements
In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. We have to do it in O(1) extra space.
Sample Testcases:
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}
EDIT: I got it in Amazon placement test. Have been trying it for a long time. PLease provide psuedo code. What i tried is finding new position p for second element e(1st is already at correct position), inserting e at p and repeating the same for the old element at position p. But this is ending in a cycle. I tried detecting cycle and incrementing the starting position by 1. But even this is not working.
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();}
This is the so called in-place in-shuffle algorithm, and it's an extremely hard task if you want to do it efficiently. I'm just posting this entry so people don't post their so called "solutions" claiming that it can be extended to work with O(1) space, without any proof...
Here is a paper for a simpler case when the list is in the form: a1 a2 a3 ... an b1 b2 b3 .. bn:
http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf
这篇关于面试测试 - 重新排列数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
