《编程珠玑》第二章——“啊哈！算法”

三个问题&＃xff1a;

1.给定一个最多包含40亿个随机排列的32位整数的顺序文件&＃xff0c;找出一个不在文件中的32位整数&＃xff08;在文件中至少缺失一个这样的数——为什么&＃xff1f;&＃xff09;。在具有足够内存的情况下&＃xff0c;如何解决该问题&＃xff1f;如果有几个外部临时文件可用&＃xff0c;但是仅有几百字节的内存&＃xff0c;又该如何解决该问题&＃xff1f;

内存足够的情况下&＃xff0c;可以采用位图法。即设一位图 至少需要 2^32/8&＃61;537MB 内存&＃xff0c;初始化位图&＃xff0c;每位设置为0。.不断从文件中读入数据&＃xff0c;并设置相应的位图数据位1。历遍位图&＃xff0c;数据位为0的即为缺失的整数。

内存不足时&＃xff0c;可以采用二分查找法。把40亿个随机数(正整数)分成两段区间&＃xff0c;[0~2^31)  和[2^31~2^32)&＃xff0c;读取文件中的数据&＃xff0c;依据数据的首位是0还是1&＃xff0c;分别划分到[0~2^31)  和[2^31~2^32)这两个区段。只要每个区段的数据个数小于2^32&＃xff0c;则必存在缺失的数据。注意&＃xff0c;区段中的个数有可能大于2^32&＃xff0c;因为数据又能存在重复&＃xff0c;书上好像没有考虑这种情况。如果两个区段数据个数都小于2^32&＃xff0c;则取其小者&＃xff0c;若一样多&＃xff0c;则随机取一个。若取的是[0~2^31) 区段&＃xff0c;则缺失的整数首位必然是0&＃xff0c;若在[2^31~2^32)区段&＃xff0c;则为1 。如此&＃xff0c;总数为n的数据&＃xff0c;缩小为 小于n/2个数据的范围。

如此反复&＃xff0c;则可找到一个缺失的数据。  时间复杂度O(n) 。

2.将一个n元一维向量向左旋转i个位置。例如&＃xff0c;当n&＃61;8且i&＃61;3时&＃xff0c;向量abcdefg旋转为defgabc。简单的代码使用一个n元的中间向量在n步内完成该工作&＃xff0c;你能否仅使用数十个额外字节的存储空间&＃xff0c;在正比于n的时间内完成向量的旋转&＃xff1f;

   咋一想&＃xff0c;搞个临时数组&＃xff0c;东挪挪西挪挪就能搞定了&＃xff0c;但必定效率低下啊。

书中说&＃xff1a;这个方法有点像精巧的杂技动作&＃xff0c;移动a[0]到临时变量t&＃xff0c;然后移动a[i]至a[0]&＃xff0c;a[2i]至a[i]&＃xff0c;依次类推&＃xff08;将a中的所有下标对n取模&＃xff09;&＃xff0c;直至返回到取a[0]中的元素&＃xff0c;此时改为从t取值然后终止过程。如果该过程没有移动全部元素&＃xff0c;就从a[1]开始再次进行移动&＃xff0c;直到所有的元素都已经移动为止。”

3.给定一个英语字典&＃xff0c;找出其中的所有变位词集合。例如&＃xff0c;“pots”&＃xff0c;“stop”&＃xff0c;“tops”互为变位词&＃xff0c;因为每一个单词都可以通过改变其他单词中的字母的顺序来得到。

“解决这个问题的许多方法都出奇地低效和复杂。任何一种考虑单词中所有字母的排列的方法都注定了要失败。而比较所有单词对的任何方法在我的机器上运行至少要花费一整夜的时间。”

我们获得的”啊哈&＃xff01;灵机一动“就是标识字典中的每一个词&＃xff0c;使得在相同变位词类中的单词具有相同的标识。然后&＃xff0c;将所有具有相同标识的单词集中在一起。这将原始的变位词问题简化为两个子问题&＃xff1a;选择标识和集中具有相同标识的单词。

对第一个问题&＃xff0c;我们可以使用基于排序的标识&＃xff1a;将单词中的字母按照字母表顺序排列。要解决第二个问题&＃xff0c;我们将所有的单词按照其标识的顺序排列。

书中的程序按照三阶段的”管道“组织&＃xff0c;其中一个程序的输出文件作为下一个程序的输入文件。第一个程序sign()直接写在main函数里来标识单词&＃xff0c;第二个程序排序sort()标识后的文件&＃xff0c;而第三个程序squash()将这些单词压缩为每个变位词类一行的形式。

程序有一些局限在于要事先输入单词的个数&＃xff0c;以for循环让输入停止&＃xff0c;而且输入单词的长度不能长于20位。