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

6、在2.5億個整數中找出不重復的整數，注，內存不足以容納這2.5億個整數。

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

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

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

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

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

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

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

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

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

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

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

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

9、上千萬或上億數據（有重復），統計其中出現次數最多的錢N個數據。

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