文件搜索索引的算法问题

Question

有一个问题,我也有解决方案.但我无法理解解决方案.请帮助一些例子和淋浴一些经验.

题

如果文件包含大约3亿个社会安全号码(9位数字),请找到一个不在文件中的9位数字.您拥有无限的驱动器空间,但只有2MB的RAM供您使用.

回答

在第一步中,我们构建一个初始化为0的数组2 ^ 16个整数,对于文件中的每个数字,我们将其16个最高有效位索引到此数组并递增数字.

由于文件中的数字少于2 ^ 32,因此数组中必须存在(至少)一个小于2 ^ 16的数字.这告诉我们这些高位中可能的数字中至少缺少一个数字.

在第二遍中,我们只关注与该标准匹配的数字,并使用大小为2 ^ 16的位向量来识别其中一个缺失的数字.

Answer 1

为了使解释更简单,假设你有一个两位数字的列表,其中每个数字在0到3之间,但你不能为16个可能的数字中的每个数字保留16位,无论你是否已经遇到了.你要做的是创建一个a由4个3位整数组成的数组,然后用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之间的差异.