在2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù),注,內(nèi)存不足以容納這2.5億個(gè)整數(shù)。
方案1:
采用2-Bitmap(每個(gè)數(shù)分配2bit,00表示不存在,01表示出現(xiàn)一次,10表示多次,11無(wú)意義)進(jìn)行,共需內(nèi)存2^32 * 2 bit=1 GB內(nèi)存,還可以接受。然后掃描這2.5億個(gè)整數(shù),查看Bitmap中相對(duì)應(yīng)位,如果是00變01,01變10,10保持不變。所描完事后,查看bitmap,把對(duì)應(yīng)位是01的整數(shù)輸出即可。
方案2:
也可采用分治,劃分小文件的方法。然后在小文件中找出不重復(fù)的整數(shù),并排序。然后再進(jìn)行歸并,注意去除重復(fù)的元素。