《算法设计手册》面试题解答 第四章:排序和搜索

4-40.

  如果给你1,000,000个整数来排序,你会选择什么算法?消耗的时间和空间呢?

解析:

  我个人倾向于用随机化的快速排序。

  首先是它在平均意义上来看比同样O(nlogn)的归并排序和堆排序快(见4-41)。 

  另外,和堆排序相比,快速排序的元素扫描是线性的,而且交换常被限制在一个有限范围内。假如这所有的整数不能存入内存,那么发生缺页中断的次数也小于堆排序。当然,当数据量更大时,问题就会牵扯到内部排序(英文维基/百度百科)和外部排序(英文维基/百度百科)的讨论。

  同时,在《编程珠玑》上看到,如果这些数字有特征,如不重复出现,且范围不是很大,那么可以设计出专门的算法来完成,比如使用位向量排序

  面试时的开放型题目,不妨尽可能广泛而深入的探讨。

 

4-41.

  分析最常见的排序算法的优点和缺点。

解析:

  这个问题老生常谈了,相关文章特别多,不打算在这里解答。

  p.s.,原书正文提到,虽然都是O(nlogn)的时间复杂度,而且最坏情况下快速排序退化为O(n2),但快速排序比归并排序和对排序在多数情况下都快2~3倍,原因是它的最内层迭代语句最简单和快速(原书4.6.3节)。

 

4-42.

  实现一个算法,返回数组中只出现一次的元素。

 解析:

  如果先排序,再遍历,时间复杂度O(nlogn)。

  如果遍历时进行hash,然后输出整个hash表,那么时间复杂度O(n)。(《剑指Offer》面试题35:第一个只出现一次的字符,这种方法可以找出所有只出现一次的字符)

  如果加上额外的条件:只有一个元素出现了一次,其他都出现了偶数次,那么把所有元素做异或,最终结果就是只出现一次的元素,时间复杂度O(n)。(《编程之美》1.5快速找出故障机器)

 

4-43.

  限制2Mb内存,如何排序一个500Mb的文件?

解析:

  正如4-40提到的,使用外部排序吧。常见的是多路归并排序,以下摘自百度百科:

外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装人内存的部分,分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行归并排序

 

4-44.

  设计一个栈,支持O(1)内完成push、pop和获得最小值min的操作。

解析:

  一般思路是维护两个栈,一个和一般的栈一样,另一个用维护每个元素压入第一个栈时的最小值。《剑指Offer》面试题21:包含min函数的栈有详细分析,下面是它的代码实现:

《算法设计手册》面试题解答 第四章:排序和搜索MinInStack

 

4-45.

  给定3个字母组成的字符串,比如ABC,和一篇文档。找出文档中的包含这3个字母的最短片段。同时,各个字母在文档中出现位置的下标已经存放在一个排序数组中,比如A:[1,4,5]。

  (补充说明)为了帮助理解原题题意,下面几个典型输入和输出。

input1: [1,10], [2,20], [3,30]

output1:[1, 3],length=3

input2:[1,9,27], [6,10,19], [8,12,14]

output2:[8, 10],length=3

input3:[1,4,11,27], [3,6,10,19], [5,8,12,14]

output3:[3, 5],length=3

input4:[1,4,5], [3,9,10], [2,6,15]

output4:[1, 3],length=3

解析:

  假定文档是CxxxAxxxBxxAxxCxBAxxxC,其中x代表非ABC的其他字母或符号。扫描过程是这样的:

C
CA
CAB - all words, length 9 (CxxxAxxxB...)
CABA - all words, length 12 (CxxxAxxxBxxA...)
CABAC - violates The Property, remove first C
ABAC - violates The Property, remove first A
BAC - all words, length 7 (...BxxAxxC...)
BACB - violates The Property, remove first B
ACB - all words, length 6 (...AxxCxB...)
ACBA - violates The Property, remove first A
CBA - all words, length 4 (...CxBA...)
CBAC - violates The Property, remove first C
BAC - all words, length 6 (...BAxxxC)

  这个过程可以总结为:

  对三个数组进行归并,维护这个归并字符串并统计归并的字符串中A、B、C的个数;

  归并时,当新加入的字符导致满足A、B、C都出现时,统计这时片段长度并与最小值比较,如果小于最小值则更新并记录开始和结尾的索引;

  当新加入的字符与归并字符串第一个字符相同时,删去第一个字符串。如果此时新的第一个字符在字符串出现次数非0,同样删去。这个过程递归进行直到首字母只出现了1次。

  继续归并直到整片文档扫描完毕。

  方法来自于*

 

  类似问题:《编程之美》3.5最短摘要的生成 

 

4-46.

  12个硬币,其中11个是重量相同的真币,另一个是假币,重量与它们不同,但可能轻了也可能重了。请用天平只称三次就确定哪个是假币。

解析:

  如果已知不标准的硬币是轻还是重,那么很简单,直接分3组,称第一二组确定出硬币在哪组,然后再组内对半称,最后再对半称。但此时不知是轻是重,这个方法不可行。

这里轻重未知,在每次称量时,应该尽量利用上次称量出的轻重关系。为了便于叙述,讲12个硬币标记为1、2、...12。先称量1+2+3+4和5+6+7+8:

如果相等,那么假币在9、10、11、12中。此时已知1~8是真币,可以作为标准来判断,那么使用1+10和2+12比较,如果相同则假币在9和11中,9和1称来判断假币是9还是11;否则用1和10来称一次判断假币是10还是12。

如果不等,假设1+2+3+4>5+6+7+8(反之类似),此时9、10、11、12是真币。那么将1、2、3去掉换成5、6、7,再在右边加上标准的9、10、11,形成5+6+7+4和9+10+11+8比较。

如果相等,假币只可能在1、2、3中,并且由第一次称量的结果,假币比真币重。从1、2、3中选择2个,若平衡,则剩余一个为假币,不平衡时重的那个是假币。

如果5+6+7+4<9+10+11+8,只可能因为轻的假币来到了左边。那么就在5、6、7中判断那个轻的假币,和上面类似。

如果5+6+7+4>9+10+11+8,5、6、7必然都不是假币,那么只用判断4和8哪个是假币。使用1枚真币和4称量即可判断。

  扩展一下,可以发现这个方法也能判断13枚的情况:先分成12枚和1枚,如果假币在12枚中,分析同上;如果假币是那分出来的1枚,上面第一种相等的情况每次都是相等,判断完三次就可得出结论:假币不在12枚中,只能是那额外的1枚。

  另外,官方wiki answer里是一个万能的分组解法,操作起来按部就班,直接根据结果查表即可,但分组理由没有详细解释,就没有深入研究。




本文转自五岳博客园博客,原文链接:http://www.cnblogs.com/wuyuegb2312/p/3263697.html,如需转载请自行联系原作者

上一篇:挖矿继续支撑着芯片厂商的销量 AMD受益最大


下一篇:python-ImportError:无法导入名称’BeautifulSoup4′