Problem I：
给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺失一个这样的数——为什么？）。在具备足够内存的情况下，如何处理该问题？假如有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何处理该问题？
首先看具备足够内存的情况，假如你认真看了我前几日写的第一篇文章，我相信你会毫不犹豫的使用位向量处理该问题。
但是，在仅有几百字节和几个外部文件的情况下，如何找到缺失的整数呢？答案是：二分搜索。当我看到二分搜索的时候，脑海里想到的就是如下图所示的内容（我相信大部分人也和我一样，由于我如同就只会将二分搜索应用到这里了；见识很重要，所以多读书！）。
在有序数组中搜索元素
我们从表示每个整数的32位的视角来考虑二分搜索。算法的第一趟（最多）读取40亿个输入整数，并把起始位为0的整数写入一个文件，把起始位为1的整数写入另一个文件。
这两个文件中，有一个文件最多包含20亿个整数，接下来选择文件size小的那一个当作输入，重复探测过程，只不过这次探测的是第二个位。假如原始的输入文件包含 n 个元素，那么第一趟将读取 n 个整数，第二趟 n/2 个整数，第三趟 n/4 个整数，依此类推，所以总的运行时间收敛于 2n，即O(n)。参考代码如下：
int BinarySearch(int* a, int* b, int* c, int alen, int bits) { int biter, citer, i; int res = 0; while (bits--) { for (i = biter = citer = 0; i < alen; ++i) { if (a[i] & (1 << bits)) { b[biter++] = a[i]; } else { c[citer++] = a[i]; } } if (biter <= citer) { res |= (1 << bits); a = b; alen = biter; } else { a = c; alen = citer; } } return res;}Problem II：
将一个 n 元一维向量向左旋转 i 个位置。例如，当 n=8 且 i=3 时，向量 abcdefgh 旋转为 defghabc。简单的代码使用一个 n 元的中间向量在 n 步内完成该工作。你是否仅使用数十个额外字节的内存，在正比于 n 的时间内完成向量的旋转？
可以通过如下方式处理该问题：首先可以将 x 的前 i 个元素复制到一个临时数组中。但是这种办法使用了 i 个额外的位置产生了过大的存储空间的消耗。 另一种方法是定义一个函数将 x 向左旋转一个位置（其时间正比于 n）而后调用该函数 i 次，但该方法产生了过大的时间消耗。
有一个成功的方法相似精巧的杂技动作：移动 x[0] 到临时变量 t，而后移动 x[i] 至 x[0]，x[2i] 至 x[i]，依此类推（将x中的所有下标对 n 取模），直至返回到取 x[0] 中的元素，此时改为从 t 取值而后终止过程。当 i 为 3 且 n 为 12 时，元素按如下顺序移动。
假如该过程没有移动一律元素，就从 x[1] 开始再次移动，直到所有的元素都已经移动为止。
//提取最大公约数 辗转相除int gcd(int i, int j) { return j == 0 ? i : gcd(j, i % j);}//method: 替换按照如下过程进行，x[0]->t, x[i]->x[0], x[2i]->x[i]...... // 一共有n与i的最大公因数趟次置换。template<typename T>void rotation(std::vector<T>& num, int i) { int size = num.size(); int times = gcd(size, i); for (int j = 0; j < times; ++j) { T temp = num[j]; int k = j; int t = 0; while (1) { /*int t = k + i; if (t >= size) { t -= size; }*/ t = (k + i) % size; if (t == j) { break; } num[k] = num[t]; k = t; } num[k] = temp; }}从另外一面考察这个问题，可以得到一个不同的算法：旋转向量 x 其实就是交换向量 ab 的两段，得到向量 ba。这里 a 代表 x 中的前 i 个元素。假设 a 比 b 短，将 b 分为 bl 和 br,使得 br 具备与 a 相同的长度。交换 a 和 br，也就将 ablbr 转换为 brbla。序列 a 此时已经处于最终的位置，因而现在的问题就集中在交换 b 的两部分。因为新问题与原来的问题具备相同的形式，递归就可。
//交换 从LStart开始和从RStart开始的字符 count次void swap(string& str, int LStart, int RStart, int count) { while (count--) { char temp = str[LStart]; str[LStart] = str[RStart]; str[RStart] = temp; LStart++; RStart++; }}void vector_rotation(string& str, int i) { int rotdist = i % str.size(); if (rotdist == 0) return; int m, n, p; m = p = rotdist; n = str.size() - m; while (m != n) { if (m < n) { swap(str, p - m, p - m + n, m); n -= m; } else { swap(str, p - m, p, n); m -= n; } } swap(str, p - m, p, m);}问题看起来很难，除非最终取得了最佳答案：我们将问题看作是把向量 ab 转换成 ba，假如我们有一个求逆函数，从 ab 开始，先对 a 求逆，得到 arb,而后对 b 求逆，得到 arbr。最后整体求逆，得到 (arbr)r。此时刚好是 ba。即：
reverse(0, i - 1); /* cbadefgh */reverse(i, n - 1); /* cbahgfed */reverse(0, n - 1); /* defghabc */翻转代码在时间和空间上都很高效，代码简短，极难出错。
Problem III：
给定一个英文字典，找出其中所有的变位词集合。例如，“pots”，“stop”和”tops“互为变位词，由于每一个单词都可以通过改变其余单词中字母的顺序来得到。
任何一种考虑单词中所有字母的排列的方法注定要失败！比方单词”abcdefghijklmno“就有15！种排列，可想而知。。。
假设一本单词簿有23 w 个单词，而比较所有单词对的任何方法也至少要运行一整夜的时间。
我们可以标识( identify )字典中的每一个词，使得在相同变位词集合中的单词具备相同的标识。而后，将所有具备相同标识的单词集中在一起。这将原始的问题转化为两个子问题：选择标识和集中具备相同标识的单词。
对于第一个子问题，我们可以使用基于排序的标识：将单词中的字母按照字母表的顺序排列。”deposit“的标识就是”deiopst“，这也是”dopiest”和其余任何在该类中的单词的标识。对于第二个子问题，我们可以将所有的单词按照其标识的顺序排序。
procedure
vector<vector<string> > ChangeWordList(const unordered_set<string>& dict) { vector<vector<string> > res; map<string, set<string> > mapper; for (auto& str : dict) { string s = str; // 排序后的s即为标识。 sort(s.begin(), s.end()); mapper[s].insert(str); } for (auto it = mapper.begin(); it != mapper.end(); ++it) { vector<string> vec((it->second).begin(), (it->second).end()); res.push_back(vec); } return res;}PS:
二分查找并没有在快速搜索有序数组这里终止，对于二分查找技术在程序设计中的应用来说，这些应用仅仅只是皮毛而已。求根程序使用二分搜索技术，通过连续地对分区间来求解单变量方程式（数值分析家称之为对分法）；其余使用二分搜索的地方包括树数据结构，程序调试等等。
翻转代码很高效，求逆代码理应作为一种常识。
当使用等价关系来定义类别时，定义一种标识使得类中的每一项都具备相同的标识，而该类以外的其余项则没有该标识，这是很有用的。
作图采用 draw.io
有什么error大家可以在评论指出来啊啊啊！！！
