啊哈！算法
最后更新于：2022-04-01 21:46:05
## 啊哈！算法
第2章围绕3个问题展开。
* 给定一个包含32位整数的顺序文件，它至多只能包含40亿个这样的整数， 并且整数的次序是随机的。请查找一个此文件中不存在的32位整数。 在有足够主存的情况下，你会如何解决这个问题？ 如果你可以使用若干外部临时文件，但可用主存却只有上百字节， 你会如何解决这个问题？
这是CTCI中的一道题目，详细解答请戳以下链接：
[请猛戳我](http://www.hawstein.com/posts/12.3.html)
* 请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8,i=3， 那么向量abcdefgh旋转之后得到向量defghabc。
这个问题很常见了，做3次翻转即可，无需额外空间：
~~~
reverse(0, i-1); // cbadefgh
reverse(i, n-1); // cbahgfed
reverse(0, n-1); // defghabc
~~~
* 给定一本英语单词词典，请找出所有的变位词集。例如，因为“pots”， “stop”，“tops”相互之间都是由另一个词的各个字母改变序列而构成的， 因此这些词相互之间就是变位词。
这个问题可以分3步来解决。第一步将每个单词按字典序排序， 做为原单词的签名，这样一来，变位词就会具有相同的签名。 第二步对所有的单词按照其签名进行排序，这样一来，变位词就会聚集到一起。 第三步将变位词分组，形成变位词集。示意图如下：
';