有一个问题,我也有解决方案.但我无法理解解决方案.请帮助一些例子和淋浴一些经验.
题
如果文件包含大约3亿个社会安全号码(9位数字),请找到一个不在文件中的9位数字.您拥有无限的驱动器空间,但只有2MB的RAM供您使用.
回答
在第一步中,我们构建一个初始化为0的数组2 ^ 16个整数,对于文件中的每个数字,我们将其16个最高有效位索引到此数组并递增数字.
由于文件中的数字少于2 ^ 32,因此数组中必须存在(至少)一个小于2 ^ 16的数字.这告诉我们这些高位中可能的数字中至少缺少一个数字.
在第二遍中,我们只关注与该标准匹配的数字,并使用大小为2 ^ 16的位向量来识别其中一个缺失的数字.
algorithm ×1