不妨假設10G個整數是64bit的。
2G內存可以存放256M個64bit整數。
我們可以將64bit的整數空間平均分成256M個取值範圍,用2G的內存對每個取值範圍內出現整數個數進行統計。這樣遍歷一邊10G整數後,我們便知道中數在那個範圍內出現,以及這個範圍內總共出現了多少個整數。
如果中數所在範圍出現的整數比較少,我們就可以對這個範圍內的整數進行排序,找到中數。如果這個範圍還可以採用同樣的方法將此範圍再次分成多個更小的範圍(256M-228,所以最多需要3次就可以將此範圍縮小到1,也就找到了中數)
分享到:
閱讀更多 lee哥說架構 的文章
