既然我们在做创造性的回答，下面是另一个问题。

使用外部排序程序对输入文件进行数字排序。这将适用于任何数量的内存(如果需要，它将使用文件存储)。 通读排序文件并输出缺少的第一个数字。

一些消除

一种方法是消除比特，但这实际上可能不会产生结果(很可能不会)。Psuedocode:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

位计数

跟踪比特数;用最少的比特来产生一个值。同样，这也不能保证生成正确的值。

范围的逻辑

跟踪列表的顺序范围(按开始顺序)。范围由结构定义:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

遍历文件中的每个值，并尝试将其从当前范围中删除。这个方法没有内存保证，但是它应该做得很好。

您可以使用位标志来标记一个整数是否存在。

遍历整个文件后，扫描每个位以确定数字是否存在。

假设每个整数是32位，如果进行了位标记，它们将方便地放入1gb RAM中。

检查输入文件的大小，然后输出任何过大而无法用该大小的文件表示的数字。这似乎是一个廉价的技巧，但它是一个创造性的解决面试问题的方法，它巧妙地避开了记忆问题，从技术上讲，它是O(n)。

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

应该打印10位计数- 1，这将永远大于2位计数。从技术上讲，你必须打败的数字是2 bitcount -(4 * 109 - 1)，因为你知道文件中还有(40亿- 1)个其他整数，即使使用完美的压缩，它们也会占用至少1位。

为什么要把它弄得这么复杂?你要的是一个文件中没有的整数?

根据指定的规则，您唯一需要存储的是到目前为止在文件中遇到的最大整数。读取整个文件后，返回一个大于1的数字。

不存在触及maxint或任何东西的风险，因为根据规则，对算法返回的整数或数字的大小没有限制。

如果我们假设数字的范围总是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;