第二章 : 啊哈, 算法

大量数据中找不存在的数

问题

一个 40 亿个随机排列的32位整数的顺序文件 , 找出一个不在文件中的32位整数

解法

利用二分查找加文件 , 第一遍遍历整个文件 , 按第1位是否为 0写入两组文件, 选数据量小的那组文件进行第二次遍历 , 依此类推

数组循环左移

问题

将一个 n 元一维向量向左旋转 i 个位置 。例如 , 当 n=8 且 i=3 时, 向量 abcdefgh 旋转为 defghabc 。

解法

如果采用记录一个中间数组的方式进行数组拼接, 当 i 很大时候会出现内存不够的情况 。这里可以把一个循环左移的问题 , 转换为一个 翻转数组的问题 。翻转一个数组能够在 n/2 次循环内完成, 完成一次左移 i 位操作需要翻转 3 次 : 即 reverse(arr[:i]), reverse(arr[:i]), reverse(a[:]) , 这样便能实现整个移位过程。