這是一個面試問題：給定一個包含40億個整數的輸入文件，提供一個算法來生成一個未包含在文件中的整數。假設您有1 GB內存。如果您只有10 MB內存，請跟進您的操作。我的分析：文件大小為4×10 9 ×4字節= 16 GB。我們可以進行外部排序，因此我們可以了解整數的范圍。我的問題是在排序的大整數集中檢測缺失整數的最佳方法是什么？我的理解（閱讀完所有答案后）：假設我們正在討論32位整數。有2 ^ 32 = 4 * 10 9個不同的整數。情況1：我們有1 GB = 1 * 10 9 * 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 * 10 6 * 8位= 8000萬位解決方案：對于所有可能的16位前綴，有2 ^ 16個整數= 65536，我們需要2 ^ 16 * 4 * 8 = 2百萬位。我們需要構建65536個桶。對于每個桶，我們需要4個字節來保存所有可能性，因為最壞的情況是所有40億個整數屬于同一個桶。通過第一次通過文件構建每個桶的計數器。掃描存儲桶，找到第一個命中率低于65536的存儲桶。構建新的存儲桶，我們在第二步中通過文件的第二次傳遞找到了高16位前綴掃描步驟3中構建的存儲桶，找到第一個沒有命中的存儲桶。代碼與上面的代碼非常相似。結論：我們通過增加文件傳遞來減少內存。對那些遲到的人的澄清：問題，并不是說文件中沒有包含一個完整的整數 - 至少不是大多數人解釋它的方式。但是，評論主題中的許多評論都是關于任務的變化。不幸的是，將其引入評論主題的評論后來被其作者刪除了，所以現在看起來孤立的回復只是誤解了一切。這很令人困惑。抱歉。