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大家可以在评论指出来啊啊啊！！！
网友评论