Chinaunix首页 | 论坛 | 博客
  • 博客访问: 587504
  • 博文数量: 165
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1554
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-23 22:57
个人简介

我本仁慈,奈何苍天不许

文章分类

全部博文(165)

文章存档

2018年(1)

2016年(33)

2015年(5)

2014年(34)

2013年(92)

分类: LINUX

2013-12-26 15:19:00

 

一年前,我们讨论过一个算法问题,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页的论文,算法那是非常的复杂,我估计贴出来都没几个人仔细看。

这一次,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

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

阅读(373) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~