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

　　·問題描述：

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

　　·解題思路：

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

　　·方法一：分治法

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

　　·方法二：位圖法

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

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