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次。
继续归并直到整片文档扫描完毕。
方法来自于stackoverflow。
类似问题：《编程之美》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，如需转载请自行联系原作者
