我得到了这个面试问题：
给定一个具有 40 亿个整数的输入文件，请提供一种算法来生成文件中不包含的整数。假设您有 1 GB 的内存。如果只有 10 MB 的内存，请继续执行下一步操作。
文件大小为 4×10 9 ×4 字节 = 16 GB。
我们可以进行外部排序，从而让我们知道整数的范围。
我的问题是在排序的大整数集中检测丢失的整数的最佳方法是什么？
假设我们正在谈论 32 位整数，那么有 2 32 = 4 * 10 9 个不同的整数。
如果我们用一位代表一个不同的整数，那就足够了。我们不需要排序。
int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
Scanner in = new Scanner(new FileReader("a.txt"));
while(in.hasNextInt()){
int n = in.nextInt();
bitfield[n/radix] |= (1 << (n%radix));
}
for(int i = 0; i< bitfield.lenght; i++){
for(int j =0; j<radix; j++){
if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
}
}
}解决方案：
对于所有可能的 16 位前缀，有 2 16个整数 = 65536，我们需要 2 16 * 4 * 8 = 2 百万个位。我们需要构建 65536 个存储桶。对于每个存储桶，我们需要 4 个字节来保存所有可能性，因为最坏的情况是所有 40 亿个整数都属于同一个存储桶。
- 通过第一次遍历文件来构建每个存储桶的计数器。
- 扫描存储桶，找到第一个命中率低于 65536 的存储桶。
- 通过在文件的第二遍中构建在步骤 2 中发现高 16 位前缀的新存储桶
- 扫描在步骤 3 中构建的存储桶，找到第一个没有命中的存储桶。
该代码与上面的代码非常相似。
结论：我们通过增加文件传递来减少内存。
对于迟到的人的澄清：问的问题不是说文件中没有正好包含一个整数 - 至少这不是大多数人的解释方式。但是，注释线程中的许多注释都与任务的这种变化有关。不幸的是，将其引入注释线程的注释后来被其作者删除了，因此现在看来，孤立的答复似乎误解了所有内容。非常令人困惑，对不起。
假设 “整数” 表示 32 位：10 MB 的空间足以让您计算输入文件中具有给定 16 位前缀的数字个数，对于一次通过的所有可能的 16 位前缀输入文件。至少有一个水桶命中率低于 2 16次。再进行一遍，以查找该存储桶中哪些可能的数字已被使用。
如果它表示大于 32 位，但仍为有界大小：请执行上述操作，忽略所有碰巧落在（有符号或无符号；您选择的）32 位范围之外的所有输入数字。
如果 “integer” 表示数学整数：请仔细阅读一次输入并跟踪您所见过的最长数字中的最大数字长度。完成后，输出最大值加一个带有一位数字的随机数。 （文件中的一个数字可能是一个大于 10 MB 的数字，要精确表示，但是如果输入是文件，则至少可以表示适合该文件的长度）。
统计确定的算法比确定性方法使用更少的遍数来解决此问题。
如果允许使用非常大的整数，则可以生成一个在 O（1）时间内可能唯一的数字。像 GUID这样的伪随机 128 位整数将仅与集合中现有的 40 亿个整数之一发生冲突，而不会发生于每 640 亿亿个案例中的十分之一。
如果整数限制为 32 位，则可以使用一次少于 10 MB 的数据生成一个唯一可能唯一的数字。伪随机 32 位整数将与 40 亿个现有整数之一相撞的几率约为 93％（4e9 / 2 ^ 32）。 1000 个伪随机整数全部发生碰撞的几率小于 12,000 万亿的整数（一次碰撞的几率 ^ 1000）。因此，如果程序维护一个包含 1000 个伪随机候选者的数据结构并迭代已知的整数，从而消除候选者中的匹配项，则几乎可以肯定找到了文件中没有的至少一个整数。
有关此问题的详细讨论，已在Jon Bentley 的“专栏 1：裂解牡蛎” 中进行了编程 Pearls Addison-Wesley pp.3-10
Bentley 讨论了几种方法，包括外部排序，使用多个外部文件进行合并排序等。但是 Bentley 建议的最佳方法是使用位字段的单次通过算法，他幽默地称其为 “Wonder Sort” ：) 来解决这个问题，有 40 亿个数字可以表示为：
4 billion bits = (4000000000 / 8) bytes = about 0.466 GB实现该位集的代码很简单：（摘自解决方案页面）
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }Bentley 的算法对文件进行一次遍历， set数组中的适当位，然后使用test宏检查该数组以查找丢失的数字。
如果可用内存小于 0.466 GB，Bentley 建议使用 k-pass 算法，该算法会根据可用内存将输入划分为多个范围。举一个非常简单的例子，如果只有 1 个字节（即用于处理 8 个数字的内存）可用并且范围从 0 到 31，我们将其分为 0 到 7、8-15、16-22 等范围。 32/8 = 4遍中的每遍处理此范围。
HTH。