今天，我們來(lái)聊一道常見(jiàn)的考題，也出現(xiàn)在騰訊面試的三面環(huán)節(jié)，非常有意思。具體的題目如下：

文件中有40億個(gè)QQ號(hào)碼，請(qǐng)?jiān)O(shè)計(jì)算法對(duì)QQ號(hào)碼去重，相同的QQ號(hào)碼僅保留一個(gè)，內(nèi)存限制1G.?

這個(gè)題目的意思應(yīng)該很清楚了，比較直白。為了便于大家理解，我來(lái)畫(huà)個(gè)動(dòng)圖玩玩，希望大家喜歡。

能否做對(duì)這道題目，很大程度上就決定了能否拿下騰訊的offer，有一定的技巧性，一起來(lái)看下吧。

在原題中，實(shí)際有40億個(gè)QQ號(hào)碼，為了方便起見(jiàn)，在圖解和敘述時(shí)，僅以4個(gè)QQ為例來(lái)說(shuō)明。

方法一：排序

很自然地，最簡(jiǎn)單的方式是對(duì)所有的QQ號(hào)碼進(jìn)行排序，重復(fù)的QQ號(hào)碼必然相鄰，保留第一個(gè)，去掉后面重復(fù)的就行。

原始的QQ號(hào)為：

排序后的QQ號(hào)為：

去重就簡(jiǎn)單了：

可是，面試官要問(wèn)你，去重一定要排序嗎？顯然，排序的時(shí)間復(fù)雜度太高了，無(wú)法通過(guò)騰訊面試。

方法二：hashmap

既然直接排序的時(shí)間復(fù)雜度太高，那就用hashmap吧，具體思路是把QQ號(hào)碼記錄到hashmap中：

mapFlag[123] = truemapFlag[567] = truemapFlag[123] = truemapFlag[890] = true

mapFlag[123] = truemapFlag[567]?=?truemapFlag[890] = true

可是，面試官又要問(wèn)你了：實(shí)際要存40億QQ號(hào)碼，1G的內(nèi)存夠分配這么多空間嗎？顯然不行，無(wú)法通過(guò)騰訊面試。

方法三：文件切割

顯然，這是海量數(shù)據(jù)問(wèn)題。看過(guò)很多面經(jīng)的求職者，自然想到文件切割的方式，避免內(nèi)存過(guò)大。

可是，絞盡腦汁思考，要么使用文件間的歸并排序，要么使用桶排序，反正最終是能排序的。

既然排序好了，那就能實(shí)現(xiàn)去重了，貌似就萬(wàn)事大吉了。我只能坦白地說(shuō)，高興得有點(diǎn)早哦。

接著，面試官又要問(wèn)你：這么多的文件操作，效率自然不高啊。顯然，無(wú)法通過(guò)騰訊面試。

方法四：bitmap

來(lái)看絕招！我們可以對(duì)hashmap進(jìn)行優(yōu)化，采用bitmap這種數(shù)據(jù)結(jié)構(gòu)，可以順利地同時(shí)解決時(shí)間問(wèn)題和空間問(wèn)題。

在很多實(shí)際項(xiàng)目中，bitmap經(jīng)常用到。我看了不少組件的源碼，發(fā)現(xiàn)很多地方都有bitmap實(shí)現(xiàn)，bitmap圖解如下：

這是一個(gè)unsigned char類型，可以看到，共有8位，取值范圍是[0, 255]，如上這個(gè)unsigned char的值是255，它能標(biāo)識(shí)0~7這些數(shù)字都存在。

同理，如下這個(gè)unsigned char類型的值是254，它對(duì)應(yīng)的含義是：1~7這些數(shù)字存在，而數(shù)字0不存在：

由此可見(jiàn)，一個(gè)unsigned char類型的數(shù)據(jù)，可以標(biāo)識(shí)0~7這8個(gè)整數(shù)的存在與否。以此類推：

• 一個(gè)unsigned int類型數(shù)據(jù)可以標(biāo)識(shí)0~31這32個(gè)整數(shù)的存在與否。

• 兩個(gè)unsigned int類型數(shù)據(jù)可以標(biāo)識(shí)0~63這64個(gè)整數(shù)的存在與否。

顯然，可以推導(dǎo)出來(lái)：512MB大小足夠標(biāo)識(shí)所有QQ號(hào)碼的存在與否，請(qǐng)注意：QQ號(hào)碼的理論最大值為2^32 - 1，大概是43億左右。

接下來(lái)的問(wèn)題就很簡(jiǎn)單了：用512MB的unsigned int數(shù)組來(lái)記錄文件中QQ號(hào)碼的存在與否，形成一個(gè)bitmap，比如：

bitmapFlag[123] = 1bitmapFlag[567] = 1bitmapFlag[123] = 1bitmapFlag[890] = 1

bitmapFlag[123] = 1bitmapFlag[567]?=?1bitmapFlag[890] = 1

擴(kuò)展練習(xí)一

文件中有40億個(gè)互不相同的QQ號(hào)碼，請(qǐng)?jiān)O(shè)計(jì)算法對(duì)QQ號(hào)碼進(jìn)行排序，內(nèi)存限制1G.?

很顯然，直接用bitmap, 標(biāo)記這40億個(gè)QQ號(hào)碼的存在性，然后從小到大遍歷正整數(shù)，當(dāng)bitmapFlag的值為1時(shí)，就輸出該值，輸出后的正整數(shù)序列就是排序后的結(jié)果。

請(qǐng)注意，這里必須限制40億個(gè)QQ號(hào)碼互不相同。通過(guò)bitmap記錄，客觀上就自動(dòng)完成了排序功能。

擴(kuò)展練習(xí)二

文件中有40億個(gè)互不相同的QQ號(hào)碼，求這些QQ號(hào)碼的中位數(shù)，內(nèi)存限制1G.?

我知道，一些刷題經(jīng)驗(yàn)豐富的人，最開(kāi)始想到的肯定是用堆或者文件切割，這明顯是犯了本本主義錯(cuò)誤。直接用bitmap排序，當(dāng)場(chǎng)搞定中位數(shù)。

擴(kuò)展練習(xí)三

文件中有40億個(gè)互不相同的QQ號(hào)碼，求這些QQ號(hào)碼的top-K，內(nèi)存限制1G.?

我知道，很多人背誦過(guò)top-K問(wèn)題，信心滿滿，想到用小頂堆或者文件切割，這明顯又是犯了本本主義錯(cuò)誤。直接用bitmap排序，當(dāng)場(chǎng)搞定top-K問(wèn)題。

擴(kuò)展練習(xí)四

文件中有80億個(gè)QQ號(hào)碼，試判斷其中是否存在相同的QQ號(hào)碼，內(nèi)存限制1G.?

我知道，一些吸取了經(jīng)驗(yàn)教訓(xùn)的人肯定說(shuō)，直接bitmap啊。然而，又一次錯(cuò)了。根據(jù)容斥原理可知：

因?yàn)镼Q號(hào)碼的個(gè)數(shù)是43億左右(理論值2^32 - 1)，所以80億個(gè)QQ號(hào)碼必然存在相同的QQ號(hào)碼。

海量數(shù)據(jù)的問(wèn)題，要具體問(wèn)題具體分析，不要眉毛胡子一把抓。有些人完全不刷題，肯定不行。有些人刷題后不加思考，不會(huì)變通，也是不行的。好了，先說(shuō)這么多。我們也會(huì)一步一個(gè)腳印，爭(zhēng)取每篇文章講清講透一件事，也希望大家閱讀后有所收獲，心情愉快。

? 耗時(shí)2年，Android進(jìn)階三部曲第三部《Android進(jìn)階指北》出版！
? 『BATcoder』做了多年安卓還沒(méi)編譯過(guò)源碼？一個(gè)視頻帶你玩轉(zhuǎn)！
? 『BATcoder』我去！安裝Ubuntu還有坑？
? 重生！進(jìn)階三部曲第一部《Android進(jìn)階之光》第2版 出版！
?BATcoder技術(shù)群，讓一部分人先進(jìn)大廠
大家好，我是劉望舒，騰訊TVP，著有三本業(yè)內(nèi)知名暢銷書(shū)，連續(xù)四年蟬聯(lián)電子工業(yè)出版社年度優(yōu)秀作者，百度百科收錄的資深技術(shù)專家。

想要加入?BATcoder技術(shù)群，公號(hào)回復(fù)BAT?即可。

為了防止失聯(lián)，歡迎關(guān)注我的小號(hào)

??微信改了推送機(jī)制，真愛(ài)請(qǐng)星標(biāo)本公號(hào)??