好的，这并没有经过充分的思考，因为它假设文件中的整数遵循某种静态分布。显然他们不需要这样做，但即使这样，也应该试试这个:

有≈43亿个32位整数。我们不知道它们在文件中是如何分布的，但最糟糕的情况是具有最高香农熵的情况:均匀分布。在这种情况下，任何一个整数不出现在文件中的概率为

((2³²-1)/2³²)⁰⁰⁰⁰≈.4

The lower the Shannon entropy, the higher this probability gets on the average, but even for this worst case we have a chance of 90% to find a nonoccurring number after 5 guesses with random integers. Just create such numbers with a pseudorandom generator, store them in a list. Then read int after int and compare it to all of your guesses. When there's a match, remove this list entry. After having been through all of the file, chances are you will have more than one guess left. Use any of them. In the rare (10% even at worst case) event of no guess remaining, get a new set of random integers, perhaps more this time (10->99%).

内存消耗:几十个字节，复杂度:O(n)，开销:neclectable，因为大部分时间将花费在不可避免的硬盘访问上，而不是比较int类型。 当我们不假设静态分布时，实际最坏的情况是每个整数都出现最大值。曾经，因为那时只有 1 - 4000000000/2³²≈6% 所有的整数都不会出现在文件中。因此，您需要更多的猜测，但这仍然不会消耗大量的内存。

如果我们假设数字的范围总是2^n(2的偶次幂)，那么排异或将成立(如另一张海报所示)。至于为什么，让我们证明一下:

这个理论

给定任何以0为基础的整数范围，其中有2^n个元素，其中缺少一个元素，您可以通过简单地将已知值乘在一起来找到缺少的元素。

证明

我们看一下n = 2。对于n=2，我们可以表示4个唯一的整数:0、1、2、3。它们有一个模式:

0-00 1-01 2-10 3-11

现在，如果我们仔细观察，每个位都被精确地设置了两次。因此，由于它被设置为偶数次，而这些数字的异或将产生0。如果缺少一个数字，排他性或将产生一个数字，当与缺少的数字排他性时，结果将为0。因此，丢失的号码和得到的排他号码完全相同。如果去掉2，得到的xor将是10(或2)。

现在来看n+1。让我们称每个比特在n中被设置的次数为x，称每个比特在n+1中被设置的次数为y。y的值将等于y = x * 2，因为有x个元素的n+1位设置为0,x个元素的n+1位设置为1。因为2x总是偶数，所以n+1总是将每一位设置为偶数次。

因此，既然n=2可行，n+1也可行，那么xor方法将适用于所有n>=2的值。

0为基础范围的算法

这很简单。它使用2*n位内存，因此对于任何<= 32的范围，2个32位整数都可以工作(忽略文件描述符消耗的任何内存)。它只对文件进行一次传递。

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

任意基范围的算法

该算法适用于任何起始数到任何结束数的范围，只要总范围等于2^n…这基本上是重新定义了范围，使最小值为0。但它确实需要遍历文件2次(第一次获取最小值，第二次计算缺少的int)。

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

任意范围

我们可以将这种修改后的方法应用于任意范围的集合，因为所有范围都会至少穿过2^n的幂次。这只适用于有一个单一的缺失位。它需要对一个未排序的文件进行2次传递，但它每次都会找到一个丢失的数字:

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

基本上，在0附近重新设置范围。然后，它在计算异或时计算要追加的未排序值的数量。然后，它将未排序值的计数加1，以处理缺少的值(计算缺少的值)。然后，继续求n的值，每次加1，直到n是2的幂。然后将结果重新基于原始基数。完成了。

下面是我在PHP中测试的算法(使用数组而不是文件，但概念相同):

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

在一个具有任何范围的值的数组中(我测试了包括负号)，其中一个在该范围内是缺失的，它每次都找到正确的值。

另一种方法

既然我们可以使用外部排序，为什么不只是检查间隙呢?如果我们假设文件在运行这个算法之前已经排序:

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;

我将回答1gb版本:

这个问题没有足够的信息，所以我将先说明一些假设:

整数为32位，取值范围为-2,147,483,648 ~ 2,147,483,647。

伪代码:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

根据原题中目前的措辞，最简单的解决方法是:

找到文件中的最大值，然后加上1。

这可以在非常小的空间内使用一种变体的二分搜索来解决。

从允许的数字范围0到4294967295开始。 计算中点。 遍历文件，计算有多少数字等于、小于或高于中点值。 如果没有相等的数字，你就完了。中点数就是答案。 否则，选择数字最少的范围，并使用这个新范围重复第2步。

这将需要对文件进行多达32次线性扫描，但它只使用几个字节的内存来存储范围和计数。

这本质上与Henning的解决方案相同，除了它使用两个箱子而不是16k。

老问题了，但我想知道“非功能性”需求。在我看来，应该给出一个线索——如果这个问题是在其他地方问的，而不是在一本书里，然后继续讨论所有的可能性的利弊。通常情况下，这似乎是在工作面试中问的，让我困惑的是，在不知道软要求的情况下，不可能给出一个明确的答案，即。“查找缺失的数字一定非常快，因为它一秒钟要使用x次。”

我想这样的问题或许可以给出一个合理的答案。

我将所有数字归并排序到一个新文件中，每个int使用4个字节。当然，一开始做起来会很慢。但是它可以用很小的内存量来完成(你不需要把所有内存都保存在RAM中) 使用二进制搜索检查数字是否存在于预排序文件中。因为每个值仍然是4个字节，这没有问题

缺点:

文件大小 第一次排序很慢——但只需要一次

优点:

查找起来非常快

这又是一个非常适合写书的问题。但我认为，当要解决的问题还不完全清楚时，在寻求单一的最佳解决方案时，这是一个奇怪的问题。