挑戰(zhàn)程序員同學，如何只用2GB內存從20/40/80億個整數中找到出現(xiàn)次數最多的數？1、4字節(jié)表示的整數數為2^32≈40億，2字節(jié)表示的無符號整數數為2^16≈60000。2、2G=2^31b≈20

挑戰(zhàn)程序員同學，如何只用2GB內存從20/40/80億個整數中找到出現(xiàn)次數最多的數？

1、4字節(jié)表示的整數數為2^32≈40億，2字節(jié)表示的無符號整數數為2^16≈60000。

2、2G=2^31b≈20億字節(jié)。

3、為了找出出現(xiàn)次數最多的數字，應記錄每個數字的出現(xiàn)次數。最快的方法是記錄每個數字在內存中出現(xiàn)的次數。記錄方法是記錄相應的存儲器地址數和相應地址的存儲器單元數。但是，2G內存只能記錄20億字節(jié)的數字，如果每個數字的出現(xiàn)次數大于255則會發(fā)生溢出，沒有風險。因此，這種方案是不可取的。

4、這樣，磁盤上只能記錄每次出現(xiàn)的次數。這樣，就在磁盤上創(chuàng)建了一個16g文件。每4個字節(jié)對應一個整數，可以對應40億個整數。用于記錄相應整數的個數。

1. 初始化文件。

2. 依次讀取數據并用無符號整數記錄在磁盤文件中。如果發(fā)生溢出，則該數字是次數最多的數字。

3. 從文件中讀取每個數字的次數，用變量a記錄最高次數，用變量B記錄最高次數的數據，用文件依次記錄最高次數的數據。當最大次數增加時，a1和B被設置為1，并且該數字被寫入文件中。當出現(xiàn)相同次數的數字b1時，該數字被寫入文件的相應位置，直到全部被讀取為止。

所以您根本不需要2G內存。