2021-04-11

编程珠玑: 啊哈！算法

三个问题

给定一个最多包含 40 亿个随机排列的 32 位整数的文件，找出一个不在文件中的 32 位整数（整个文件可能有多个不存在的整数，但是只需要找到一个）。如果给定内存足够，如何处理；如果内存限定在几百字节，但是磁盘容量没有限制，如何处理？
将一个 n 元一维向量向左旋转 i 个位置。例如，向量 abcdefgh 中 n = 8, i = 3，那么旋转后的向量为 defghabc。
给定一个英文字典，找出其中所有变位词集合。如 post, stop, tops 互为变位词，因为每个单词都可以通过改变其他单词中字母的位置来得到。

二分搜索

二分搜索的初始条件是已知一个对象存在于一个给定的范围内，而一次探测操作可以帮助我们明确该对象是否低于，高于或者等于给定的位置。二分搜索通过重复探测当前范围的中点来定位对象，如果此次探测没有找到该对象，那么我们将当前范围减半，然后继续下一次探测。当我们找到需要的对象或者当前范围为空时停止。

二分搜索比较常见的应用是在有序的数组中搜索元素。

顺序搜索在搜索一个具有 n 个元素的表时，平均需要进行 n/2 次比较，二分搜索进行不超过 logn 次比较即可

关于第一个问题，我们需要找出一个不存在该文件中的 32 位整数，如果有足够的内存，我们可以采用位图技术，使用 > 500MB 的内存形成位图来表示已经看到的整数。

那么对于只用几百字节内存的情况下，为了采用二分搜索技术，我们需要做到：

定义一个范围
在该范围内表示元素的方式
用来确定哪一半范围存在缺失整数的探测方法

思路

我们从表示每个整数的 32 位的视角来考虑二分搜索。算法的第一趟最多读取 40 亿个输入整数，并把起始位为 0 的整数写入一个顺序文件，把起始位为 1 的整数写入另一个顺序文件。

											 ---> 为 0 的位
当前输入 ---> 0/1 探测 --
                       ---> 为 1 的位

在这两个文件中，有一个文件最多包含 20 亿个整数，接下来把包含数据少的文件用作当前输入并重复探测过程，但是这次探测的是第二个位。

如果两个文件数据大小相同，则随机选择一个文件，因为这两个文件都缺失数字

如果原始的输入文件包含 n 个元素，那么第一趟读取 n 个元素，第二趟最多读取 n/2 个元素，第三趟最多读取 n/4 个元素，以此类推，总运行时间正比于 n。

通过排序文件并扫描，也能找到缺失的整数，但是运行时间是 O(nlogn)

二分搜索还有很多别的应用，比如求根，随机二分搜索。

向量旋转

问题二解决思路有多种：

先将前 i 个元素复制到临时数组中，之后将剩余的 n-i 个元素左移 i 个位置，最后将临时数组中的前 i 个元素复制到原数组的后 i 个位置
定义一个方法 func(x)，该方法用于将数组 x 左旋一位（时间复杂度为 O(n)），之后重复调用该函数 i 次
将原数组 x 分为 ab 两段（a 的长度为 i，b 的长度为 n-i），那么原来的问题就变成将 ab 转化成 ba。首先对 a 求逆得到 a^rb，之后对 b 求逆得到 a^rb^r，最后对整体求逆得到 (a^rb^r)^r，此时正好为 ba。
```
 reverse(0, i-1);
 reverse(i, n-1);
 reverse(0, n-1);
```

第一种方法使用了额外的 i 长度的数组，会导致较大的内存消耗；方法二时间复杂度较大 O(i*n)；第三种方法完整代码为：

private static void reverse(int[] x, int i) {
    reverse(x, 0, i - 1);
    reverse(x, i, x.length - 1);
    reverse(x, 0, x.length - 1);
}

private static void reverse(int[] x, int start, int end) {
    while (start < end) {
        int tmp = x[start];
        x[start] = x[end];
        x[end] = tmp;
        start++;
        end--;
    }
}

扩展

如何将向量 abc 转换成向量 cba?

存在恒等式：(a^rb^rc^r)^r = cba。因此，分别对 a, b, c 求逆，再对整体求逆，即可得到 cba.

排序

第三个问题有一种思路：利用回溯算法找出给定单词中所有字母的排列，之后再与给定的单词进行比对。如果单词长度比较短，可以尝试，但是如果单词比较长，假设为 20 个字母，那么每个单词的排列组合共有 $20!$ 种。只是计算排列组合就需要消耗大量的时间，显然不可取。

考虑以下思路：

对每个单词进行标识，这样相同变位词类中的单词具有相同的标识
将相同标识的单词集合

单词的标识也有不同的考虑：

基于排序的标识：deposit 的标识是 deiopst，dopiest 的标识也是 deiopst
基于计数的标识：mississippi 的标识为 i4m1p2s4

原理

排序

排序用来产生有序的输出，用于将相等的元素集中在一起
二分搜索

可以高效地在有序表中查找元素，可用于基于内存或者磁盘排序。
标识

当使用等价关系来定义类时，通过定义一种标识使得同类中每一项都具有相同的标识，而其他类的标识则不同。