十道面試題與十個海量數(shù)據(jù)處理方法總結(jié)(2)

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

    方案1：采用2-Bitmap（每個數(shù)分配2bit，00表示不存在，01表示出現(xiàn)一次，10表示多次，11無意義）進(jìn)行，共需內(nèi)存2^32 * 2 bit=1 GB內(nèi)存，還可以接受。然后掃描這2.5億個整數(shù)，查看Bitmap中相對應(yīng)位，如果是00變01，01變10，10保持不變。所描完事后，查看bitmap，把對應(yīng)位是01的整數(shù)輸出即可。

    方案2：也可采用與第1題類似的方法，進(jìn)行劃分小文件的方法。然后在小文件中找出不重復(fù)的整數(shù)，并排序。然后再進(jìn)行歸并，注意去除重復(fù)的元素。

7、騰訊面試題：給40億個不重復(fù)的unsigned int的整數(shù)，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當(dāng)中？

    與上第6題類似，我的第一反應(yīng)時快速排序+二分查找。以下是其它更好的方法：
    方案1：oo，申請512M的內(nèi)存，一個bit位代表一個unsigned int值。讀入40億個數(shù)，設(shè)置相應(yīng)的bit位，讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1，為1表示存在，為0表示不存在。

    dizengrong：
    方案2：這個問題在《編程珠璣》里有很好的描述，大家可以參考下面的思路，探討一下：
又因為2^32為40億多，所以給定一個數(shù)可能在，也可能不在其中；
這里我們把40億個數(shù)中的每一個用32位的二進(jìn)制來表示
假設(shè)這40億個數(shù)開始放在一個文件中。

    然后將這40億個數(shù)分成兩類:
      1.最高位為0
      2.最高位為1
    并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)<=20億，而另一個>=20億（這相當(dāng)于折半了）；
與要查找的數(shù)的最高位比較并接著進(jìn)入相應(yīng)的文件再查找

    再然后把這個文件為又分成兩類:
      1.次最高位為0
      2.次最高位為1

    并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)<=10億，而另一個>=10億（這相當(dāng)于折半了）；
    與要查找的數(shù)的次最高位比較并接著進(jìn)入相應(yīng)的文件再查找。
    .......
    以此類推，就可以找到了,而且時間復(fù)雜度為O(logn)，方案2完。

   附：這里，再簡單介紹下，位圖方法：
    使用位圖法判斷整形數(shù)組是否存在重復(fù) 
    判斷集合中存在重復(fù)是常見編程任務(wù)之一，當(dāng)集合中數(shù)據(jù)量比較大時我們通常希望少進(jìn)行幾次掃描，這時雙重循環(huán)法就不可取了。

    位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個長度為max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到5就給新數(shù)組的第六個元素置1，這樣下次再遇到5想置位時發(fā)現(xiàn)新數(shù)組的第六個元素已經(jīng)是1了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復(fù)。這種給新數(shù)組初始化時置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長的話效率還能提高一倍。

    歡迎，有更好的思路，或方法，共同交流。

8、怎么在海量數(shù)據(jù)中找出重復(fù)次數(shù)最多的一個？
   
    方案1：先做hash，然后求模映射為小文件，求出每個小文件中重復(fù)次數(shù)最多的一個，并記錄重復(fù)次數(shù)。然后找出上一步求出的數(shù)據(jù)中重復(fù)次數(shù)最多的一個就是所求（具體參考前面的題）。

9、上千萬或上億數(shù)據(jù)（有重復(fù)），統(tǒng)計其中出現(xiàn)次數(shù)最多的錢N個數(shù)據(jù)。

    方案1：上千萬或上億的數(shù)據(jù)，現(xiàn)在的機(jī)器的內(nèi)存應(yīng)該能存下。所以考慮采用hash_map/搜索二叉樹/紅黑樹等來進(jìn)行統(tǒng)計次數(shù)。然后就是取出前N個出現(xiàn)次數(shù)最多的數(shù)據(jù)了，可以用第2題提到的堆機(jī)制完成。