为了完整起见，这里提供另一种非常简单的解决方案，它很可能需要很长时间才能运行，但使用的内存非常少。

让所有可能的整数成为int_min到int_max的范围，并且bool isNotInFile(integer)是一个函数，如果文件不包含某个整数，则返回true，否则返回false（通过将某个整数与文件中的每个整数进行比较）

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

你可以使用位标志来标记一个整数是否存在。
在遍历整个文件后，扫描每一位以确定数字是否存在。
假设每个整数占32位，如果进行位标记，它们将方便地适合1GB的RAM。

我将回答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;
    }
}

针对10 MB内存限制的解决方法如下：

1. 将数字转为二进制表示。
2. 创建一个二叉树，其中左子树为0，右子树为1。
3. 使用其二进制表示将每个数字插入到树中。
4. 如果一个数字已经被插入，则叶子节点已经被创建。

完成后，只需选择之前未创建过的路径来创建所需数字。
40亿个数字=2 ^ 32，这意味着10 MB可能不足够。
编辑：
如果两端叶子节点已经被创建，并且具有共同的父节点，则可以删除它们并标记父节点为非解决方案。 这样可以减少分支并减少内存需求。
第二次编辑：
也没有必要完全构建整棵树。 只有在数字相似的情况下，才需要构建深度分支。 如果我们也剪枝，那么这个解决方案实际上可能会起作用。

正如Ryan所说，基本上是对文件进行排序，然后遍历整数，当有一个值被跳过时，那么它就是我们要找的值:)

编辑面向downvoters(点踩者）：OP提到了文件可以被排序，因此这是一种有效的方法。

只要我们想出创意答案，这里就有另一种方法。
使用外部排序程序按数字对输入文件进行排序。这适用于您可能拥有的任何内存量（如果需要，它将使用文件存储）。 阅读排序后的文件并输出第一个缺失的数字。

我认为这是一个已解决的问题（见上文），但有一个有趣的特殊情况需要考虑，因为它可能会被问到：

如果存在确切的 4,294,967,295（2^32 - 1）个 32 位整数没有重复，因此只缺少一个，那么就有一个简单的解决方案。

从零开始运行总数，并对文件中的每个整数进行操作，使用 32 位溢出加法（实际上，runningTotal = (runningTotal + nextInteger) % 4294967296）。完成后，再使用 32 位溢出加法将 4294967296/2 添加到运行总数中。从 4294967296 中减去这个和，结果就是缺失的整数。

"仅缺少一个整数" 的问题可以在一次运行中解决，且仅需要 64 位 RAM 来存储数据（32 位用于计算运行总数，32 位用于读取下一个整数）。

推论：如果我们不关心整数结果需要具有多少位，则更通用的规范非常简单。我们只需生成足够大的整数，使其不能包含在我们获得的文件中。同样，这占用的 RAM 绝对最少。请参见伪代码。

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

位数消除

一种方法是通过消除位数来减小数据量，但这并不一定会产生结果（很可能不会）。伪代码：

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 };

遍历文件中的每个值，尝试将其从当前范围中移除。该方法没有内存保证，但应该表现相当不错。

2^128*1018 + 1（即（2⁸）^16*1018 + 1）- 这难道不可能是今天的普遍答案吗？这代表一个数字，无法在任何当前文件系统中的16 EB文件中保存。

给定一个包含 40 亿个整数的输入文件，提供一种算法生成一个不在该文件中的整数。假设你有 1 GiB 的内存。如果你只有 10 MiB 的内存，你会怎么做？文件大小为 16 GiB（4 * 109 * 4 字节）。针对 32 位无符号整数。

0 <= Number < 2^32
0 <= Number < 4,294,967,296

我的解决方案：没有错误检查的C++。

#include <vector>
#include <fstream>
#include <iostream>
using namespace std;

int main ()
{
    const long SIZE = 1L << 32;

    std::vector<bool> checker(SIZE, false);

    std::ifstream infile("file.txt");  // TODO: error checking

    unsigned int num = 0;

    while (infile >> num)
    {
        checker[num] = true ;
    }

    infile.close();

    // print missing numbers

    for (long i = 0; i < SIZE; i++)
    {
        if (!checker[i])
            cout << i << endl ;
    }

    return 0;
}

复杂度

• 空间 ~ 2³² 位 = 2²⁹ 字节 = 2¹⁹ 千字节 = 2⁹ 兆字节 = 1/2 千兆字节
• 时间 ~ 单次遍历
• 完备性 ~ 是