第二章呢，是以三个问题展开的。
第一个问题：给定的最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（至少有一个整数，因为32位的整数，一共会有2的32次方个整数，即4 294 967 296）。在足够的内存空间情况下，如何解决问题？如果有几个外部的临时文件可用，但仅有几百字节的内存，又该如何解决？
对于有足够内存的情况下，可以用刚刚的位图数据结构的办法，可以用536 870 912个8位字节形成位图来表示已看到的整数。
但是内存不足的时候呢，我没有想到这种办法，因为我纠结在了32位整数，到底是说的是32位二进制形式表示的整数呢，还是32位的正整数呢，我以为是正整数了，然后就没想到，但是却被不是计算机专业的男朋友想出来了。。。唉唉唉。。。
曾经在《算法艺术与信息学竞赛》中看到了一个题目，跟这个很类似，只不过数量要小很多。有16个正整数，有一个缺失，怎么找到。
这两个都是一个类型的题目，都是找缺失的数。
首先，用0 1表示的整数，从低位到高位，0跟1的数量是固定的，比如16位整数中，最低位0有8个，1有8个，如果查完之后，0只有7个，那缺的数肯定在以0结尾的数中，依次次下去就找到了。
这里也是用的二分查找的思想。而我在数据结构书上学的二分查找，有一些限制条件：必须是顺序存储的，必须是有序的。而这个题，每个32位数在文件上的存储是没有任何顺序的。关键用二分查找，是要确定一个范围，在这个范围内怎么表示数据，怎么确定哪一半范围有我们要找的数或没有我们要找的数。
比如这个题目：一开始的范围是整个文件，表示元素的方式是：01序列表示正整数，如何确定进而减少查找范围呢，根据0 1的数量来判断。
第二个题目：
将一个n元一维向量向左旋转i个位置，例如当n=8，i=3时，向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。你能否仅使用额外字节的存储空间，在正比于n的时间内完成向量的旋转。
第一种想法：也是最简单的，把前i个元素复制到一个临时数组中，然后将余下的n-i个元素依次前移，再把临时数组中的i个元素复制到剩余的位置。但是这样用了大量的额外空间。
第二种想法：实现一个可以每次旋转1个位置的函数，调用i次，但是时间又很消耗。
第三种想法：很像杂技操作哦。首先，将x[0]移动到临时变量t中，然后移动x[i]到x[0],x[2i]到x[i],x[3i]移动到[x2i]....依次类推，直到取到x[0]时，结束。当2i,3i,4i,等大于n时，要对n取模。
这个想法，只用了一个临时变量的额外空间。是通过数组自己来回移动，而改变顺序的，有点类似于堆排序中的数组移动。
第四种想法：从另外一种想法去思考问题，可以带来另一种思路：旋转向量x其实就是把ab变成ba,可以把x分成a bl br，交换a跟br，那么就变成了br bl a,还剩下交换bl br,就变成了，bl br a,可以利用递归。
第五种办法：求逆。ab,先对a求逆，再对b求逆，在对整体求逆，(a的逆b的逆）的逆=ba.
正相当于翻手算法：
这个翻手算法时间跟空间上都很高效的。
第三个：给定一个英语字典，找出其中的所有的变位词集合，比如“pots"和“stop”和“tops”是变位词。
关于这个问题，我一开始的思路是：给26个英文字母分别赋予一个数字表示，然后对于每个单词的每个字母都相加作为索引，然后根据索引值排序，然后就找的到了，但是这里有个问题，怎么给26个字母赋值才能让她们最后相加的不一样是个问题，因为2+2=4，1+3=4，所以很难去平衡。
可以利用翻手方法啊，先把每个单词按字母顺序排序，然后再对整体进行排序。就是先进行一种排序（水平翻手），再进行另一种排序（垂直翻手）。
这种方法很好哦。