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

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

一、用4字節(jié)表示的整數(shù)個數(shù)為2^32≈40億，而用2字節(jié)表示的無符號整數(shù)個數(shù)為2^16≈6萬。

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

三、要找出出現(xiàn)次數(shù)最多的數(shù)，則應記錄每個數(shù)出現(xiàn)的次數(shù)，最快的方法是在內存中將每個數(shù)出現(xiàn)的次數(shù)記錄下來，記錄的方法則是內存地址對應數(shù)，相應地址的內存單元記錄次數(shù)，但2G內存以字節(jié)為單位僅能記錄20億個數(shù)，且每個數(shù)出現(xiàn)的次數(shù)大于255將會出現(xiàn)溢出風險。因此，這一方案不可取。

四、這樣只能將每個次出現(xiàn)的次數(shù)記錄在磁盤上。這樣在磁盤上建一個16G的文件，每4字節(jié)對應一個整數(shù)，可對應40億個整數(shù)，并用于記錄相應整數(shù)的出現(xiàn)的次數(shù)。

1、將文件初始化。

2、依次讀取數(shù)據(jù)，并用無符號整數(shù)記錄在磁盤文件中，如出現(xiàn)溢出，則該數(shù)為次數(shù)最多的數(shù)。

3、從文件中讀取各數(shù)出現(xiàn)的次數(shù)，用一個變量A記錄最高次數(shù)，再用一個變量B記錄最高次數(shù)出現(xiàn)的數(shù)據(jù)個數(shù)，要用個文件依次記錄最高次數(shù)出現(xiàn)的數(shù)。當最高次數(shù)增加時，A 1，B置1，文件中寫入該數(shù)，同次數(shù)的數(shù)出現(xiàn)時，B 1，文件相應位置寫入該數(shù)，直到全部讀完。

這樣根本不需2G內存。

一表示什么，從總數(shù)里面去掉一部分？

"部分數(shù)"和"總數(shù)"是分析加減法應用題的數(shù)量關系用到的概念。例如：小華有20本課外書，借給同學5本，還剩幾本？在這道題中，“20本”是總數(shù)，借出的5本是一部分，剩下的是另一部分，借出的和剩下的都是部分數(shù)。數(shù)量關系式是：部分數(shù) 另一部分數(shù)＝總數(shù)總數(shù)-部分數(shù)＝另一部分數(shù)求“還剩幾本”就是求另一部分數(shù)是多少，20-5＝15，剩下15本。