有一个问题，我也有解决方案。但我无法理解解决方案。请帮助一些例子和淋浴一些经验。
题
给定一个包含大约3亿个社会安全号码（9位数字）的文件，找到一个不在文件中的9位数字。您拥有无限的驱动器空间，但只有2MB的RAM供您使用。
回答
在第一步中，我们构建一个初始化为0的数组2 ^ 16个整数，对于文件中的每个数字，我们将其16个最高有效位索引到此数组并递增数字。
由于文件中的数字少于2 ^ 32，因此数组中必须存在（至少）一个小于2 ^ 16的数字。这告诉我们在这些高位中可能的数字中至少缺少一个数字。
在第二遍中，我们只关注与该标准匹配的数字，并使用大小为2 ^ 16的位向量来识别缺失的数字之一。
为了使解释更简单，假设你有一个两位数字的列表，其中每个数字在0到3之间，但你不能为16个可能的数字中的每个数字保留16位，无论你是否已经遇到了。你要做的是创建一个数组 a 4个3位整数和in a[i]，你用第一个数字存储多少个数字 i 你遇到过（两位整数是不够的，因为你需要值0,4和它们之间的所有数字。）
如果你有这个文件
00,12,303,31,01,32,02
你的数组看起来像这样：
4,1,0,2
现在您知道所有以0开头的数字都在文件中，但是对于剩下的每个数字，至少有一个丢失。我们选择1.我们知道至少有一个以1开头的数字不在文件中。因此，创建一个4位的数组，对于每个以1开始的数字设置相应的位，最后选择一个未设置的位，在我们的示例中，如果可能为0.现在我们有了解决方案：10 。
在这种情况下，使用此方法是12位和16位之间的差异。使用您的数字，它是32 kB和119 MB之间的差异。
为了使解释更简单，假设你有一个两位数字的列表，其中每个数字在0到3之间，但你不能为16个可能的数字中的每个数字保留16位，无论你是否已经遇到了。你要做的是创建一个数组 a 4个3位整数和in a[i]，你用第一个数字存储多少个数字 i 你遇到过（两位整数是不够的，因为你需要值0,4和它们之间的所有数字。）
如果你有这个文件
00,12,303,31,01,32,02
你的数组看起来像这样：
4,1,0,2
现在您知道所有以0开头的数字都在文件中，但是对于剩下的每个数字，至少有一个丢失。我们选择1.我们知道至少有一个以1开头的数字不在文件中。因此，创建一个4位的数组，对于每个以1开始的数字设置相应的位，最后选择一个未设置的位，在我们的示例中，如果可能为0.现在我们有了解决方案：10 。
在这种情况下，使用此方法是12位和16位之间的差异。使用您的数字，它是32 kB和119 MB之间的差异。
从圆形的角度来看，假设没有重复数据，则大约有1/3的数字存在于文件中。
我们的想法是对数据进行两次传递。将每个数字视为32位（无符号）数字。在第一遍中，记录在最重要的16位中有多少个数字具有相同的数字。在实践中，将存在许多代码，其中存在零（例如，所有那些用于10位SSN的代码;很可能，所有那些第一位数为零的代码也都丢失了）。但是在具有非零计数的范围中，大多数将不具有65536个条目，如果该范围中没有间隙，则将显示多少条目。所以，稍加注意，你可以选择其中一个范围集中在第二遍。
如果幸运的话，您可以在100,000,000..999,999,999中找到零项的范围 - 您可以选择该范围内的任何数字作为缺失。
假设你不是那么幸运，选择一个位数最少的一个（或任何一个小于65536个条目）;称之为目标范围。将数组重置为全零。重读数据。如果您阅读的数字不在目标范围内，请忽略它。如果它在该范围内，则通过将数组的值设置为1来记录数字，以获得该数字的低16位。当您读取整个文件时，数组中带零的任何数字表示缺少SSN。