如何在大量的數(shù)據(jù)中找出不重復(fù)的整數(shù)?

　　·問(wèn)題描述：

　　在2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)，注意，內(nèi)存不足以容納這2.5億個(gè)整數(shù)。

　　·解題思路：

　　因?yàn)檫@道題目闡明無(wú)法一次把所有數(shù)據(jù)加載到內(nèi)存中，因此我們可以采用分治法和位圖法進(jìn)行求解。

　　·方法一：分治法

　　利用Hash的方法，把這2.5億個(gè)數(shù)劃分到更小的文件中，以確保每個(gè)文件的大小超過(guò)可用的內(nèi)存大小。接著針對(duì)每個(gè)小文件來(lái)說(shuō)，所有的數(shù)據(jù)可以一次性被加載到內(nèi)存中，因此可以使用字典或者set來(lái)找到每個(gè)小文件中不重復(fù)的數(shù)。當(dāng)處理完所有的文件后就可以找出這2.5億個(gè)整數(shù)中所有的不重復(fù)的數(shù)。

　　·方法二：位圖法

　　對(duì)于整數(shù)相關(guān)算法的求解，位圖法是一種非常實(shí)用的算法。對(duì)于本題來(lái)說(shuō)，如果可用的內(nèi)存空間超過(guò)1GB就可以使用這種方法。具體思路是：假設(shè)整數(shù)占用4B(如果占用8B，那么求解思路類(lèi)似，只不過(guò)需要占用更大的內(nèi)存)，4B也就是32位，可以表示的整數(shù)的個(gè)數(shù)為2的32次冪。因?yàn)檫@道題是查找不重復(fù)的數(shù)，而不關(guān)心具體數(shù)字出現(xiàn)的次數(shù)，因此可以分別使用2bit來(lái)表示各個(gè)數(shù)字的狀態(tài)：用00表示這個(gè)數(shù)字沒(méi)有出現(xiàn)過(guò)，01表示出現(xiàn)過(guò)1次，10表示出現(xiàn)了多次，11暫不使用。

　　根據(jù)上面的邏輯，在遍歷2.5億個(gè)整數(shù)的時(shí)候，如果這個(gè)整數(shù)對(duì)應(yīng)的為圖中的位為00，那么修改成01，如果為01那么修改為10，如果為10那么保持原值不變。這樣當(dāng)所有數(shù)據(jù)遍歷完成后，可以再遍歷一遍位圖，位圖中為01的對(duì)應(yīng)的數(shù)字就是沒(méi)有重復(fù)的數(shù)字。