《编程珠玑》笔记

Column 1. Cracking the oyster
问题：
    输入：7位电话号码的数据文件，纪录数量是百万级的；
    输出：排序后的数据文件；
    限制：内存只有2M，尽量快速；
分析：
后面有七位数字，它们的范围是[0, 9999999]，，纪录个数是千万级，而1M内存能存储25000个整数。
该问题的本质是数学上的Dense-Set，可以用Bit Map(或者叫Bit Vector)解决，方法如下：
    1)根据数据范围，建立一个BIT MAP，电话的范围是 1000000~9999999 ，那么建立含一千万个bit的数据结构bit _bit[10000000]，初使化为全0。
    2)对于数据文件里的每个 i, 将_bit[i]置为1
    3)输出
看起来好像挺复杂，实际上想法很简单，举个例子就全都懂了：
{1,3,5,9}可以用向量表示为  0 1 0 1 0 1 0 0 0 1
这样，2M的存储空间大约可以用来表示2*8M=16M个数字。

Column 2.Aha! Algorithms
问题1:
    输入：一个包含有40亿个int的数据文件
    输出：它所遗漏的一个数字
    限制：几K的内存
分析：
    如果不限制内存，可以用位图法(需要2^32 bit = 512MB)。但内存限制在几K了怎么办？
    答案是：二分查找法！！
    取中位数0，统计大于0和小于0的数的数目，比较它们，在数目较小的范围内继续查找，直到找到遗漏的数。
扩展：
    二分查找有很多直觉想不到的应用，如上述问题、程序调错等等，在实际中应注意它的应用。

问题2：
   输入：一个串(如abcdefgh), 数i
   输出：defghabc
   限制：
分析：略

问题3.
   输入：包含大量单词的文件
   输出：所有同文词（包含字母和个数相同的词，如tab、bat和abt等）
   分析：将单词按照字母大小重新排列，如tab重排得到abt，bat重排也是abt。具体方法略。