生成一个不在四十亿个给定整数中的整数
我被问到这个面试问题：
给定一个包含40亿个整数的输入文件，提供一个算法来生成一个文件中不包含的整数。假设您有1 GB内存。跟进如果您只有10 MB内存的操作。
我的分析：
文件大小为4×109×4字节=16 GB。
我们可以进行外部排序，从而让我们知道整数的范围。
我的问题是，在排序的大整数集中检测缺失整数的最佳方法是什么？
我的理解（看完所有答案后）：
假设我们谈论的是32位整数，有232=4*109不同的整数。
案例1：我们有1 GB=1*109*8位=80亿位内存。
解决方案：
如果我们使用一个位表示一个不同的整数，这就足够了。我们不需要排序。
执行：
int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
Scanner in = new Scanner(new FileReader("a.txt"));
while(in.hasNextInt()){
int n = in.nextInt();
bitfield[n/radix] |= (1 << (n%radix));
}
for(int i = 0; i< bitfield.lenght; i++){
for(int j =0; j<radix; j++){
if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
}
}
}
情况2:10 MB内存=10*106*8位=8000万位
解决方案：
对于所有可能的16位前缀，有216数量的 integers=65536，我们需要216*4*8=200万位。我们需要构建65536个桶。对于每个桶，我们需要4个字节来保存所有可能性，因为最坏的情况是所有40亿整数都属于同一个桶。
- 通过第一次遍历文件构建每个存储桶的计数器。
- 扫描桶，找到第一个命中率小于65536的人。
- 构建我们在步骤2中找到的高16位前缀的新存储桶 通过文件的第二次传递
- 扫描步骤3中构建的桶，找到第一个没有的桶 有一个命中。
代码与上面的代码非常相似。
结论： 我们通过增加文件传递来减少内存。
对迟到的人澄清一下：正如所问的，这个问题并没有说只有一个整数不包含在文件中——至少大多数人不是这样解释的。然而，评论线程是中的许多评论关于该任务的变化。不幸的是，介绍到评论线程的评论后来被其作者删除了，所以现在看起来孤立的回复只是误解了一切。这非常令人困惑，对不起。
最佳答案