騰訊三面：40億個QQ號碼如何去重？
在騰訊面試的三面環(huán)節(jié)，非常有意思。具體的題目如下：
文件中有40億個QQ號碼，請設(shè)計算法對QQ號碼去重，相同的QQ號碼僅保留一個，內(nèi)存限制1G.
這個題目的意思應(yīng)該很清楚了，比較直白。為了便于大家理解，我來畫個動圖玩玩，希望大家喜歡。
在原題中，實際有40億個QQ號碼，為了方便起見，在圖解和敘述時，僅以4個QQ為例來說明。
方法一：排序
很自然地，最簡單的方式是對所有的QQ號碼進行排序，重復(fù)的QQ號碼必然相鄰，保留第一個，去掉后面重復(fù)的就行。
原始的QQ號為：
排序后的QQ號為：
去重就簡單了：
可是，面試官要問你，去重一定要排序嗎？顯然，排序的時間復(fù)雜度太高了，無法通過騰訊面試。
方法二：hashmap
既然直接排序的時間復(fù)雜度太高，那就用hashmap吧，具體思路是把QQ號碼記錄到hashmap中：
mapFlag[123] = true
mapFlag[567] = true
mapFlag[123] = true
mapFlag[890] = true由于hashmap的去重性質(zhì)，可知實際自動變成了：
mapFlag[123] = true
mapFlag[567] = true
mapFlag[890] = true很顯然，只有123，567，890存在，所以這也就是去重后的結(jié)果。
可是，面試官又要問你了：實際要存40億QQ號碼，1G的內(nèi)存夠分配這么多空間嗎？顯然不行，無法通過騰訊面試。
方法三：bitmap
來看絕招！我們可以對hashmap進行優(yōu)化，采用bitmap這種數(shù)據(jù)結(jié)構(gòu)，可以順利地同時解決時間問題和空間問題。
在很多實際項目中，bitmap經(jīng)常用到。我看了不少組件的源碼，發(fā)現(xiàn)很多地方都有bitmap實現(xiàn)，bitmap圖解如下：
這是一個unsigned char類型，可以看到，共有8位，取值范圍是[0, 255]，如上這個unsigned char的值是255，它能標(biāo)識0~7這些數(shù)字都存在。
