80億個整數中找到出現次數最多的數？

需求：

使用2G的內存，找出80億個數字中出現最多的數字。

假設：

整數為4字節（2^32=4G），即最大40多億。所有的數字有80億個。所有數字在硬盤中，本身不會占用內存。所用內存為2G多一些，例如有限的變量。但多出的內存和2G相比可以忽略不計。

設計：

80億的計數可以用4字節保存（2^32=4G）。因為如果計數超過一半，則表明該數字一定是出現最多的。2G的內存約可以保存5億多數字的計數（2G/4=512M）。

也就是說，將2G的內存分成單位為4字節的數組，可以一次獲得0～5億多之間出現最多的數字。

步驟：

順序掃描80億個數字，忽略0～512M之外的數字，每個數字N的出現個數累加存放在第N個數組元素中。最后將最出現最多的數字及其次數保存起來，出現并列第一時，只保存第一個數字。如果過程中某數字出現個數超過40億，則直接結束。再次掃描所有數字，此次忽略512M～1G之外的數字。每個數字N的出現個數累加存放在第N-512M個數組元素中。本輪所獲得的數字的出現個數和第一輪結果比較，保存較大的那個。由于整數取值范圍為4G，所以最多掃描8次后即可獲得最終結果。

問題：

如果整數長度為8字節，則需要掃描約300多億次（2^64/512M=2^40）。所以此算法并不適用于8字節的整數。

討論：

當數字足夠多，且數字取值范圍足夠大時，以有限內存獲取出現次數最多的數字幾乎是不可能的。因為數字的取值范圍極大，且數字極多，任何哈希或其它分片的算法都有可能出現極端情況，導致分片數據過多而無法一次性導入內存計算。除非我們預先知道部分數字規律，否則考慮到效率，應該只會要求得到近似結果。