今天没讲，我們來聊一道常見的考題，也出現(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)該很清楚了于样，比較直白。
能否做對(duì)這道題目，很大程度上就決定了能否拿下騰訊的offer，有一定的技巧性沙廉，一起來看下吧尖坤。
在原題中，實(shí)際有40億個(gè)QQ號(hào)碼焊唬，為了方便起見，在圖解和敘述時(shí)，僅以4個(gè)QQ為例來說明啄刹。
方法一：排序
很自然地，最簡(jiǎn)單的方式是對(duì)所有的QQ號(hào)碼進(jìn)行排序凄贩，重復(fù)的QQ號(hào)碼必然相鄰誓军，保留第一個(gè)，去掉后面重復(fù)的就行疲扎。
原始的QQ號(hào)為：
排序后的QQ號(hào)為：
去重就簡(jiǎn)單了：
可是昵时，面試官要問你，去重一定要排序嗎椒丧？顯然壹甥，排序的時(shí)間復(fù)雜度太高了，無法通過騰訊面試壶熏。
方法二：hashmap
既然直接排序的時(shí)間復(fù)雜度太高句柠，那就用hashmap吧，具體思路是把QQ號(hào)碼記錄到hashmap中：
mapFlag[123] = true mapFlag[567] = true mapFlag[123] = true mapFlag[890] = true
由于hashmap的去重性質(zhì)棒假，可知實(shí)際自動(dòng)變成了：
mapFlag[123] = true mapFlag[567] = true mapFlag[890] = true
很顯然溯职，只有123，567帽哑，890存在谜酒，所以這也就是去重后的結(jié)果。
可是妻枕，面試官又要問你了：實(shí)際要存40億QQ號(hào)碼僻族，1G的內(nèi)存夠分配這么多空間嗎？顯然不行屡谐，無法通過騰訊面試述么。
方法三：文件切割
顯然，這是海量數(shù)據(jù)問題愕掏《让兀看過很多面經(jīng)的求職者，自然想到文件切割的方式亭珍，避免內(nèi)存過大敷钾。
可是枝哄，絞盡腦汁思考，要么使用文件間的歸并排序阻荒，要么使用桶排序挠锥，反正最終是能排序的。
既然排序好了侨赡，那就能實(shí)現(xiàn)去重了蓖租，貌似就萬事大吉了。我只能坦白地說羊壹，高興得有點(diǎn)早哦蓖宦。
接著，面試官又要問你：這么多的文件操作油猫，效率自然不高啊稠茂。顯然，無法通過騰訊面試情妖。
方法四：bitmap
來看絕招睬关！我們可以對(duì)hashmap進(jìn)行優(yōu)化，采用bitmap這種數(shù)據(jù)結(jié)構(gòu)毡证，可以順利地同時(shí)解決時(shí)間問題和空間問題电爹。
在很多實(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不存在：
由此可見夜惭，一個(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)出來：512MB大小足夠標(biāo)識(shí)所有QQ號(hào)碼的存在與否敢会，請(qǐng)注意：QQ號(hào)碼的理論最大值為2^32 - 1曾沈，大概是43億左右。
接下來的問題就很簡(jiǎn)單了：用512MB的unsigned int數(shù)組來記錄文件中QQ號(hào)碼的存在與否鸥昏，形成一個(gè)bitmap塞俱，比如：
bitmapFlag[123] = 1 bitmapFlag[567] = 1 bitmapFlag[123] = 1 bitmapFlag[890] = 1
實(shí)際上就是：
bitmapFlag[123] = 1 bitmapFlag[567] = 1 bitmapFlag[890] = 1
然后從小到大遍歷所有正整數(shù)(4字節(jié))，當(dāng)bitmapFlag值為1時(shí)吏垮，就表明該數(shù)是存在的障涯。
而且，從上面的過程可以看到膳汪，自動(dòng)實(shí)現(xiàn)了去重唯蝶。顯然，這種方式可以通過騰訊的面試遗嗽。
擴(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)碼互不相同搁料。通過bitmap記錄，客觀上就自動(dòng)完成了排序功能系羞。
擴(kuò)展練習(xí)二
文件中有40億個(gè)互不相同的QQ號(hào)碼郭计，求這些QQ號(hào)碼的中位數(shù)，內(nèi)存限制1G.
我知道椒振，一些刷題經(jīng)驗(yàn)豐富的人昭伸，最開始想到的肯定是用堆或者文件切割，這明顯是犯了本本主義錯(cuò)誤澎迎。直接用bitmap排序庐杨，當(dāng)場(chǎng)搞定中位數(shù)。
擴(kuò)展練習(xí)三
文件中有40億個(gè)互不相同的QQ號(hào)碼夹供，求這些QQ號(hào)碼的top-K灵份，內(nèi)存限制1G.
我知道，很多人背誦過top-K問題哮洽，信心滿滿填渠，想到用小頂堆或者文件切割，這明顯又是犯了本本主義錯(cuò)誤。直接用bitmap排序氛什，當(dāng)場(chǎng)搞定top-K問題莺葫。
擴(kuò)展練習(xí)四
文件中有80億個(gè)QQ號(hào)碼，試判斷其中是否存在相同的QQ號(hào)碼枪眉，內(nèi)存限制1G.
我知道捺檬，一些吸取了經(jīng)驗(yàn)教訓(xùn)的人肯定說，直接bitmap啊瑰谜。然而欺冀，又一次錯(cuò)了。根據(jù)容斥原理可知：
因?yàn)镼Q號(hào)碼的個(gè)數(shù)是43億左右(理論值2^32 - 1)萨脑，所以80億個(gè)QQ號(hào)碼必然存在相同的QQ號(hào)碼隐轩。
海量數(shù)據(jù)的問題，要具體問題具體分析渤早，不要眉毛胡子一把抓职车。有些人完全不刷題，肯定不行鹊杖。有些人刷題后不加思考悴灵，不會(huì)變通，也是不行的骂蓖。好了积瞒，先說這么多。我們也會(huì)一步一個(gè)腳印登下，爭(zhēng)取每篇文章講清講透一件事茫孔，也希望大家閱讀后有所收獲，心情愉快被芳。
