首页 > 代码库 > 完美洗牌算饭
完美洗牌算饭
被大腾讯问到了完美洗牌算法,瞬间就跪了,其实原来看过,只可惜都忘了啊,现在在补充进来吧。
其实完美洗牌算法,应该给我说明白题,最少举个例子吧,当时确实大意了,也没问清楚就直接不会了,其实题意是有个长度为2n的数组{a1,a2,a3,a4,..,an,b1,b2,b3,b4,...,bn},希望排序后{a1,b1,a2,b2,...,an,bn},最好要求时间复杂度为O(n),空间复杂度为O(1)。
解法一:蛮力交换方法
1.1 说白了就是b1和a2,a3,a4,...,an交换,然后是b2和a3,a4,a5,...,an交换,直到bn不交换。复杂度O(n2),肯定不行。
1.2中间交换
交换中间的元素方法,例如:
a1,a2,a3,a4,b1,b2,b3,b4交换a4,b1为:a1,a2,a3,b1,a4,b2,b3,b4
交换中间两个,交换a3,b1和a4,b2为a1,a2,b1,a3,b2,a4,b3,b4,
下一次交换中间三个,依次增加,最后即可但时间复杂度依然为O(n2)
解法二:完美洗牌算法O(n)
有人研究出了完美洗牌算法可以将a1,a2,a3,a4,b1,b2,b3,b4通过O(n)变成b1,a1,b2,a2,b3,a4,b4,a4,通过两两交换即可完成a1,b1,a2,b2,a3,b3,a4,b4.这里来说一下如何用O(n)完成。
2.1 位置置换算法,需要空间复杂度O(n),时间复杂度O(n)
原序:a1,a2,a3,a4,b1,b2,b3,b4
位置:1, 2 , 3, 4 , 5 , 6 , 7 , 8
修改:b1,a1,b2,a2,b3,a3,b4,a4
可以看出1->2;2->4,3->6,4->8,5->1,6->3,7->5,8->7上即第i个元素放到了第(2*i)%(2*n+1)位置上
代码:
1 void pefect_shuffle1(int *a,int n){2 int n2=n*2,i,b[N];3 for(int i=1;i<=n2;i++)4 {5 b[(i*2)%(n2+1)]=a[i];6 }7 for(int i=1;i<=n2;i++)8 a[i]=b[i];9 }
我们注意到:1->2->4->8->7->5->1;和3->6->3这就是完美洗牌的关键后面继续说。
2.2 分治处理O(nlogn)
可以将大问题化成两个子问题处理,例如:
n=4情况
a1,a2,a3,a4,b1,b2,b3,b4,交换前半段的后n/2和后半段的前n/2为a1,a2,b1,b2,a3,a4,b3,b4就变成两个子问题。
n=5情况
a1,a2,a3,a4,a5,b1,b2,b3,b4,b5,将中间的给放到最后,剩下的前移即:a1,a2,a3,a4,b1,b2,b3,b4,b5,a5,变成处理n=4情况
1 #include <iostream> 2 using namespace std; 3 void perfect_shuffle2(int *a ,int n) 4 { 5 int t,i; 6 if(n==1) 7 { 8 swap(a[1],a[2]); 9 return;10 }11 int n2=n*2,n3=n/2;12 if(n%2==1)13 {14 t=a[n];15 for(i=n+1;i<=n2;i++)16 {17 a[i-1]=a[i];18 }19 a[n2]=t;20 --n;21 }22 for(i=n3+1;i<=n;i++)23 {24 t=a[i];25 a[i]=a[i+n3];26 a[i+n3]=t;27 }28 perfect_shuffle2(a,n3);29 perfect_shuffle2(a+n,n3);30 }
时间复杂度O(nlogn),空间不算递归调用栈的话为O(1)
2.3 真正完美算法O(n),O(1)
利用走圈方法:
1->2->4->8->7->5->1;
3->6->3;
1 void circle_leader(int *a ,int form ,int mod) //mod=2*n+1 2 { 3 int last=a[from],t,i; 4 for(i=from*2%mod;i!=from;i=i*2%mod) 5 { 6 t=a[i]; 7 a[i]=last; 8 last=t; 9 }10 a[from]=last;11 }
神级结论:若2*n=(3^k-1),则可以确定圈的个数及各自头部的起始位置
对于2*n=(3^k-1)这种长度的数组,恰好只有k个圈,且每个圈头部的起始位置分别为:1,3,9,...,3^(k-1)。
完美洗牌算饭