java2億個(gè)隨機(jī)生成的無(wú)序整數(shù)，如何找到其中位數(shù)？因?yàn)檫@2億個(gè)數(shù)都是無(wú)序整數(shù)，所以要先用數(shù)組排序，再取中間兩個(gè)數(shù)的平均值。挑戰(zhàn)程序員同學(xué)，如何只用2GB內(nèi)存從20/40/80億個(gè)整數(shù)中找到出現(xiàn)次數(shù)最

java2億個(gè)隨機(jī)生成的無(wú)序整數(shù)，如何找到其中位數(shù)？

因?yàn)檫@2億個(gè)數(shù)都是無(wú)序整數(shù)，所以要先用數(shù)組排序，再取中間兩個(gè)數(shù)的平均值。

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

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

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

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

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

1、將文件初始化。

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

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

這樣根本不需2G內(nèi)存。