v******y
发帖数: 22 | 1 Re-arrange array inplace from "a0a1..anb0b1..bn" to "a0b0a1b1..anbn".
Is there any solution better than O(n^2) ? | p*****n
发帖数: 368 | 2 这种题估计就是每次对半分，然后递归，总的complexity变成O(nlogn)
【在 v******y 的大作中提到】
: Re-arrange array inplace from "a0a1..anb0b1..bn" to "a0b0a1b1..anbn".
: Is there any solution better than O(n^2) ?
| k*n
发帖数: 150 | 3 there is an O(N) solution
if n satisfies some conditions (I forgot it, maybe n=3**k-1)
then you can do it perfectly by move a1 to a2 and a2 to a4 ...
and finally when some Xn come back to a1, during this process, no 'collision
' occurs, which means for any Xn, when you want to put it into a new
position Ym,
this Ym position is not the original Ym, but has been transpositioned.
So this is a perfect transposition, with O(n) time and O(1) space complexity.
Having known this, to solve a problem with arbitrary n, just do tail
recursion.
【在 v******y 的大作中提到】
: Re-arrange array inplace from "a0a1..anb0b1..bn" to "a0b0a1b1..anbn".
: Is there any solution better than O(n^2) ?
| c*b
发帖数: 3126 | 4 In-place shuffle
http://en.wikipedia.org/wiki/In_shuffle
Reference里面有O(n)的算法
【在 v******y 的大作中提到】
: Re-arrange array inplace from "a0a1..anb0b1..bn" to "a0b0a1b1..anbn".
: Is there any solution better than O(n^2) ?
| f*******n
发帖数: 8 | 5 我贴一下O（n）算法的实现吧，大家自己琢磨
#include "stdio.h"
//轮换
void Cycle(int Data[],int Lenth,int Start)
{
int Cur_index,Temp1,Temp2;
Cur_index=(Start*2)%(Lenth+1);
Temp1=Data[Cur_index-1];
Data[Cur_index-1]=Data[Start-1];
while(Cur_index!=Start)
{
Temp2=Data[(Cur_index*2)%(Lenth+1
)-1];
Data[(Cur_index*2)%(Lenth+1)
-1]=Temp1;
Temp1=Temp2;
Cur_index=(Cur_index*2)%(Lenth+1);
}
}
//数组循环移位 参考编程珠玑
void Reverse(int Data[],int Len)
{
int i,Temp;
for(i=0;i
{
Temp=Data[i];
Data[i]=Data[Len-i-1];
Data[Len-i-1]=Temp;
}
}
void ShiftN(int Data[],int Len,int N)
{
Reverse(Data,Len-N);
Reverse(&Data[Len-N],N);
Reverse(Data,Len);
}
//满足Lenth=3^k-1的perfect shfulle的实现
void Perfect1(int Data[],int Lenth)
{
int i=1;
if(Lenth==2)
{
i=Data[Lenth-1];
Data[Lenth-1]=Data[Lenth-2];
Data[Lenth-2]=i;
return;
}
while(i
{
Cycle(Data,Lenth,i);
i=i*3;
}
}
//查找最接近N的3^k
int LookUp(int N)
{
int i=3;
while(i<=N+1) i*=3;
if(i>3) i=i/3;
return i;
}
void perfect(int Data[],int Lenth)
{
int i,startPos=0;
while(startPos
{
i=LookUp(Lenth-startPos);
ShiftN(&Data[startPos+(i-1)/2],(Lenth-startPos
)/2,(i-1)/2);
Perfect1(&Data[startPos],i-1);
startPos+=(i-1);
}
}
#define N 100
void main()
{
int data[N]={0};
int i=0;
int n;
printf("please input the number of data you wanna to test
(should less than 100):\n");
scanf("%d",&n);
if(n&1)
{
printf("sorry,the number should
be even ");
return;
}
for(i=0;i
data[i]=i+1;
perfect(data,n);
for(i=0;i
printf("%d ",data[i]);
} | z***e
发帖数: 5393 | 6 我搞不懂为什么对于3^k-1的n，就可以不断地shift之后再cycle，然后就perfect
shuffle了？
【在 f*******n 的大作中提到】
: 我贴一下O（n）算法的实现吧，大家自己琢磨
: #include "stdio.h"
: //轮换
: void Cycle(int Data[],int Lenth,int Start)
: {
: int Cur_index,Temp1,Temp2;
: Cur_index=(Start*2)%(Lenth+1);
: Temp1=Data[Cur_index-1];
: Data[Cur_index-1]=Data[Start-1];
:
|
|
