Perfect Shuffle的算法

作者:, 发表于

珍爱生命,远离政治。我们继续讨论算法。

2008/04/01补充:此算法有重大缺陷。详情请见留言部分。

一年前,我们讨论过一个算法问题,perfect shuffle,据称是个微软面试题:

输入 \(a_1,a_2,\cdots,a_n,b_1,\cdots,b_n\) ,如何用 \(O(n)\) 的时间, \(O(1)\) 的空间,将这个序列顺序改为 \(a_1,b_1,\cdots,a_n,b_n\)

那一次讨论我们翻出了问题的来源,一篇长达12页的论文Computing the Cycles in the Perfect Shuffle Permutation,算法那是非常的复杂,我估计贴出来都没几个人仔细看。

这一次,Xie Xie(没错,又是他 :) )翻出了Art of Computer Programming, Volume 3上的一个难度为40分的Merge Sort习题:

已知数列 \(x_1\leq x_2\leq \cdots x_M, x_{M+1}\leq x_{M+2}\leq\cdots\leq x_n\) ,设计算法使得在线性时间,常数空间实现归并,也就是将原数组排序。

而Perfect Shuffle问题是可以规约到这个Merge Sort问题的:

mergeSort(x[1...2n]); // if this function solve Merge Sort problem
perfectShuffle(x[1...2n]): // then this solve Perfect Shuffle problem
     m <- max(x[1...2n])+1;
     x[i] <- x[i]+(2i-1)m, 
     x[i+n] <- x[i+n] + 2im
     mergeSort(x[1...2n])
     x[i] <- x[i]%m

原来我还不相信这个问题会是一个面试题。现在我信了。因为那个归并排序的算法还是有些牛人会知道的。

很好很强大。

 

另注:从2006年4月1号愚人节开始,阅微堂成立两周年了。

过去一年,阅微堂共发表了201篇文章,其中包括Liu Tao先生的19篇文章,sog white的17篇文章,以及一些授权转载的网友原创作品。共3389条留言。

感谢大家的关注和对阅微堂的支持。

Q.E.D.


上一篇:素数筛法的复杂度2008年3月30日
Xie Xie给我看了一个链接性能调优--永远超乎想象,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的。 所谓素数筛法就是那个求小于n

下一篇:有序矩阵的中位数算法2008年6月9日
给定$$n\times n$$的实数矩阵,每行和每列都是递增的,求这$$n^2$$个数的中位数。 使用类似Tarjan的线性中位数的方法,每次找每列中位数,然后找中位数


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。