[導(dǎo)讀]今天，我們來聊一道常見的考題，也出現(xiàn)在騰訊面試的三面環(huán)節(jié)，非常有意思。具體的題目如下：文件中有40億個QQ號碼，請設(shè)計算法對QQ號碼去重，相同的QQ號碼僅保留一個，內(nèi)存限制1G.?這個題目的意思應(yīng)該很清楚了，比較直白。為了便于大家理解，我來畫個動圖玩玩，希望大家喜歡。能否做對這道...
今天，我們來聊一道常見的考題，也出現(xiàn)在騰訊面試的三面環(huán)節(jié)，非常有意思。具體的題目如下：文件中有40億個QQ號碼，請設(shè)計算法對QQ號碼去重，相同的QQ號碼僅保留一個，內(nèi)存限制1G.?這個題目的意思應(yīng)該很清楚了，比較直白。為了便于大家理解，我來畫個動圖玩玩，希望大家喜歡。能否做對這道題目，很大程度上就決定了能否拿下騰訊的offer，有一定的技巧性，一起來看下吧。在原題中，實際有40億個QQ號碼，為了方便起見，在圖解和敘述時，僅以4個QQ為例來說明。
方法一：排序
很自然地，最簡單的方式是對所有的QQ號碼進(jìn)行排序，重復(fù)的QQ號碼必然相鄰，保留第一個，去掉后面重復(fù)的就行。原始的QQ號為：
排序后的QQ號為：
去重就簡單了：可是，面試官要問你，去重一定要排序嗎？顯然，排序的時間復(fù)雜度太高了，無法通過騰訊面試。方法二：hashmap
既然直接排序的時間復(fù)雜度太高，那就用hashmap吧，具體思路是把QQ號碼記錄到hashmap中：mapFlag[123] = truemapFlag[567] = truemapFlag[123] = truemapFlag[890] = true由于hashmap的去重性質(zhì)，可知實際自動變成了：mapFlag[123] = truemapFlag[567]?=?truemapFlag[890] = true很顯然，只有123，567，890存在，所以這也就是去重后的結(jié)果。可是，面試官又要問你了：實際要存40億QQ號碼，1G的內(nèi)存夠分配這么多空間嗎？顯然不行，無法通過騰訊面試。方法三：文件切割
顯然，這是海量數(shù)據(jù)問題?？催^很多面經(jīng)的求職者，自然想到文件切割的方式，避免內(nèi)存過大。
可是，絞盡腦汁思考，要么使用文件間的歸并排序，要么使用桶排序，反正最終是能排序的。既然排序好了，那就能實現(xiàn)去重了，貌似就萬事大吉了。我只能坦白地說，高興得有點早哦。接著，面試官又要問你：這么多的文件操作，效率自然不高啊。顯然，無法通過騰訊面試。方法四：bitmap
來看絕招！我們可以對hashmap進(jìn)行優(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ù)字都存在。同理，如下這個unsigned char類型的值是254，它對應(yīng)的含義是：1~7這些數(shù)字存在，而數(shù)字0不存在：由此可見，一個unsigned char類型的數(shù)據(jù)，可以標(biāo)識0~7這8個整數(shù)的存在與否。以此類推：- 一個unsigned int類型數(shù)據(jù)可以標(biāo)識0~31這32個整數(shù)的存在與否。
- 兩個unsigned int類型數(shù)據(jù)可以標(biāo)識0~63這64個整數(shù)的存在與否。
顯然，可以推導(dǎo)出來：512MB大小足夠標(biāo)識所有QQ號碼的存在與否，請注意：QQ號碼的理論最大值為2^32 - 1，大概是43億左右。接下來的問題就很簡單了：用512MB的unsigned int數(shù)組來記錄文件中QQ號碼的存在與否，形成一個bitmap，比如：bitmapFlag[123] = 1bitmapFlag[567] = 1bitmapFlag[123] = 1bitmapFlag[890] = 1實際上就是：bitmapFlag[123] = 1bitmapFlag[567]?=?1bitmapFlag[890] = 1然后從小到大遍歷所有正整數(shù)(4字節(jié))，當(dāng)bitmapFlag值為1時，就表明該數(shù)是存在的。而且，從上面的過程可以看到，自動實現(xiàn)了去重。顯然，這種方式可以通過騰訊的面試。
擴展練習(xí)一
文件中有40億個互不相同的QQ號碼，請設(shè)計算法對QQ號碼進(jìn)行排序，內(nèi)存限制1G.?很顯然，直接用bitmap, 標(biāo)記這40億個QQ號碼的存在性，然后從小到大遍歷正整數(shù)，當(dāng)bitmapFlag的值為1時，就輸出該值，輸出后的正整數(shù)序列就是排序后的結(jié)果。請注意，這里必須限制40億個QQ號碼互不相同。通過bitmap記錄，客觀上就自動完成了排序功能。擴展練習(xí)二
文件中有40億個互不相同的QQ號碼，求這些QQ號碼的中位數(shù)，內(nèi)存限制1G.?我知道，一些刷題經(jīng)驗豐富的人，最開始想到的肯定是用堆或者文件切割，這明顯是犯了本本主義錯誤。直接用bitmap排序，當(dāng)場搞定中位數(shù)。
擴展練習(xí)三
文件中有40億個互不相同的QQ號碼，求這些QQ號碼的top-K，內(nèi)存限制1G.?我知道，很多人背誦過top-K問題，信心滿滿，想到用小頂堆或者文件切割，這明顯又是犯了本本主義錯誤。直接用bitmap排序，當(dāng)場搞定top-K問題。擴展練習(xí)四
文件中有80億個QQ號碼，試判斷其中是否存在相同的QQ號碼，內(nèi)存限制1G.?我知道，一些吸取了經(jīng)驗教訓(xùn)的人肯定說，直接bitmap啊。然而，又一次錯了。根據(jù)容斥原理可知：因為QQ號碼的個數(shù)是43億左右(理論值2^32 - 1)，所以80億個QQ號碼必然存在相同的QQ號碼。海量數(shù)據(jù)的問題，要具體問題具體分析，不要眉毛胡子一把抓。有些人完全不刷題，肯定不行。有些人刷題后不加思考，不會變通，也是不行的。好了，先說這么多。我們也會一步一個腳印，爭取每篇文章講清講透一件事，也希望大家閱讀后有所收獲，心情愉快。
本站聲明： 本文章由作者或相關(guān)機構(gòu)授權(quán)發(fā)布，目的在于傳遞更多信息，并不代表本站贊同其觀點，本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者，如若文章內(nèi)容侵犯您的權(quán)益，請及時聯(lián)系本站刪除。
LED驅(qū)動電源的輸入包括高壓工頻交流(即市電)、低壓直流、高壓直流、低壓高頻交流(如電子變壓器的輸出)等。
關(guān)鍵字：
驅(qū)動電源
在工業(yè)自動化蓬勃發(fā)展的當(dāng)下，工業(yè)電機作為核心動力設(shè)備，其驅(qū)動電源的性能直接關(guān)系到整個系統(tǒng)的穩(wěn)定性和可靠性。其中，反電動勢抑制與過流保護(hù)是驅(qū)動電源設(shè)計中至關(guān)重要的兩個環(huán)節(jié)，集成化方案的設(shè)計成為提升電機驅(qū)動性能的關(guān)鍵。
關(guān)鍵字：
工業(yè)電機
驅(qū)動電源
LED 驅(qū)動電源作為 LED 照明系統(tǒng)的 “心臟”，其穩(wěn)定性直接決定了整個照明設(shè)備的使用壽命。然而，在實際應(yīng)用中，LED 驅(qū)動電源易損壞的問題卻十分常見，不僅增加了維護(hù)成本，還影響了用戶體驗。要解決這一問題，需從設(shè)計、生...
關(guān)鍵字：
驅(qū)動電源
照明系統(tǒng)
散熱
根據(jù)LED驅(qū)動電源的公式，電感內(nèi)電流波動大小和電感值成反比，輸出紋波和輸出電容值成反比。所以加大電感值和輸出電容值可以減小紋波。
關(guān)鍵字：
LED
設(shè)計
驅(qū)動電源
電動汽車(EV)作為新能源汽車的重要代表，正逐漸成為全球汽車產(chǎn)業(yè)的重要發(fā)展方向。電動汽車的核心技術(shù)之一是電機驅(qū)動控制系統(tǒng)，而絕緣柵雙極型晶體管(IGBT)作為電機驅(qū)動系統(tǒng)中的關(guān)鍵元件，其性能直接影響到電動汽車的動力性能和...
關(guān)鍵字：
電動汽車
新能源
驅(qū)動電源
在現(xiàn)代城市建設(shè)中，街道及停車場照明作為基礎(chǔ)設(shè)施的重要組成部分，其質(zhì)量和效率直接關(guān)系到城市的公共安全、居民生活質(zhì)量和能源利用效率。隨著科技的進(jìn)步，高亮度白光發(fā)光二極管(LED)因其獨特的優(yōu)勢逐漸取代傳統(tǒng)光源，成為大功率區(qū)域...
關(guān)鍵字：
發(fā)光二極管
驅(qū)動電源
LED
在LED照明技術(shù)日益普及的今天，LED驅(qū)動電源的電磁干擾(EMI)問題成為了一個不可忽視的挑戰(zhàn)。電磁干擾不僅會影響LED燈具的正常工作，還可能對周圍電子設(shè)備造成不利影響，甚至引發(fā)系統(tǒng)故障。因此，采取有效的硬件措施來解決L...
關(guān)鍵字：
LED照明技術(shù)
電磁干擾
驅(qū)動電源
開關(guān)電源具有效率高的特性,而且開關(guān)電源的變壓器體積比串聯(lián)穩(wěn)壓型電源的要小得多,電源電路比較整潔,整機重量也有所下降,所以,現(xiàn)在的LED驅(qū)動電源
關(guān)鍵字：
LED
驅(qū)動電源
開關(guān)電源
LED驅(qū)動電源是把電源供應(yīng)轉(zhuǎn)換為特定的電壓電流以驅(qū)動LED發(fā)光的電壓轉(zhuǎn)換器，通常情況下：LED驅(qū)動電源的輸入包括高壓工頻交流(即市電)、低壓直流、高壓直流、低壓高頻交流(如電子變壓器的輸出)等。
關(guān)鍵字：
LED
隧道燈
驅(qū)動電源
LED驅(qū)動電源在LED照明系統(tǒng)中扮演著至關(guān)重要的角色。由于LED具有節(jié)能、環(huán)保、長壽命等優(yōu)點，使得LED照明在各個領(lǐng)域得到廣泛應(yīng)用。然而，LED的電流、電壓特性需要特定的驅(qū)動電源才能正常工作。本文將介紹常用的LED驅(qū)動電...
關(guān)鍵字：
LED驅(qū)動電源
led照明
LED驅(qū)動電源是把電源供應(yīng)轉(zhuǎn)換為特定的電壓電流以驅(qū)動LED發(fā)光的電源轉(zhuǎn)換器，通常情況下：LED驅(qū)動電源的輸入包括高壓工頻交流(即市電)、低壓直流、高壓直流、低壓高頻交流(如電子變壓器的輸出)等。
關(guān)鍵字：
LED
驅(qū)動電源
高壓工頻交流
崧盛股份9日發(fā)布投資者關(guān)系活動記錄表，就植物照明發(fā)展趨勢、行業(yè)壁壘等問題進(jìn)行分享。植物照明未來市場需求廣闊崧盛股份指出，植物照明將會走向長期產(chǎn)業(yè)領(lǐng)域。主要原因有三：第一，LED植物照明賦能終端種植更具有經(jīng)濟價值。由于LE...
關(guān)鍵字：
崧盛股份
驅(qū)動電源
在當(dāng)今高度發(fā)展的技術(shù)中，電子產(chǎn)品的升級越來越快，LED燈技術(shù)也在不斷發(fā)展，這使我們的城市變得豐富多彩。 LED驅(qū)動電源將電源轉(zhuǎn)換為特定的電壓和電流，以驅(qū)動LED發(fā)光。通常情況下：LED驅(qū)動電源的輸入包括高壓工頻交流電(即...
關(guān)鍵字：
LED
驅(qū)動電源
高壓直流
人類社會的進(jìn)步離不開社會上各行各業(yè)的努力，各種各樣的電子產(chǎn)品的更新?lián)Q代離不開我們的設(shè)計者的努力，其實很多人并不會去了解電子產(chǎn)品的組成，比如LED電源。
關(guān)鍵字：
LED
驅(qū)動電源
低壓直流
隨著科學(xué)技術(shù)的發(fā)展，LED技術(shù)也在不斷發(fā)展，為我們的生活帶來各種便利，為我們提供各種各樣生活信息，造福著我們?nèi)祟悺ED驅(qū)動電源實際上是一種電源，但是它是一種特定的電源，用于驅(qū)動LED發(fā)射帶有電壓或電流的光。 因此，LE...
關(guān)鍵字：
LED
驅(qū)動電源
電流
LED燈作為一種新型節(jié)能和無污染光源，由于其特有的發(fā)光照明特性，在現(xiàn)代照明應(yīng)用中發(fā)揮著革命性的作用。作為 LED 照明產(chǎn)業(yè)鏈中最為核心的部件之一，LED 驅(qū)動電源的驅(qū)動控制技術(shù)所存在的可靠性低、成本高等典型問題一直制約著...
關(guān)鍵字：
多路
LED
驅(qū)動電源
隨著社會的快速發(fā)展，LED技術(shù)也在飛速發(fā)展，為我們的城市的燈光煥發(fā)光彩，讓我們的生活越來越有趣，那么你知道LED需要LED驅(qū)動電源嗎?那么你知道什么是LED驅(qū)動電源嗎?
關(guān)鍵字：
LED
開關(guān)電源
驅(qū)動電源
早前有新聞稱，Cree在2018年開始宣布轉(zhuǎn)型高科技半導(dǎo)體領(lǐng)域，并一邊逐漸脫離照明與LED相關(guān)業(yè)務(wù)，一邊持續(xù)投資半導(dǎo)體。在今日，Cree宣布與SMART Global Holdings, Inc.達(dá)成最終協(xié)議，擬將LED...
關(guān)鍵字：
cree
led照明
下載文檔
