從10G個數中找到中數在一個檔案中有10G個整數,亂序排列,要求找出中位數。記憶體限制為2G

不妨假設10G個整數是64bit的。

2G記憶體可以存放256M個64bit整數。

我們可以将64bit的整數空間平均分成256M個取值範圍,用2G的記憶體對每個取值範圍内出現整數個數進行統計。這樣周遊一邊10G整數後,我們便知道中數在那個範圍内出現,以及這個範圍内總共出現了多少個整數。

如果中數所在範圍出現的整數比較少,我們就可以對這個範圍内的整數進行排序,找到中數。如果這個範圍還可以采用同樣的方法将此範圍再次分成多個更小的範圍(256M-228,是以最多需要3次就可以将此範圍縮小到1,也就找到了中數)