力扣 692巧用小頂堆高效求解前K個(gè)高頻單詞 前言Bilibili 同步視頻 算法核心場(chǎng)景與解題痛點(diǎn)剖析1. 問(wèn)題場(chǎng)景定義2. 傳統(tǒng)解法弊端?? 核心算法原理圖文拆解1. 算法整體流程示意圖Plain Text2. 分步原理深度解析? 第一步哈希表遍歷精準(zhǔn)統(tǒng)計(jì)詞頻? 第二步自定義小頂堆篩選TopK元素? 第三步二次規(guī)整排序輸出標(biāo)準(zhǔn)結(jié)果 C 完整可運(yùn)行代碼實(shí)現(xiàn)? 算法性能復(fù)雜度分析1. 時(shí)間復(fù)雜度2. 空間復(fù)雜度 拓展答疑與學(xué)習(xí)干貨1. 可否用Map替代UnorderedMap2. 直接全局排序可行嗎3. 堆排序是最優(yōu)排序算法嗎 編程學(xué)習(xí)核心感悟 總結(jié) 前言在算法刷題與工程開(kāi)發(fā)之中詞頻統(tǒng)計(jì)、高頻元素篩選是極為經(jīng)典的核心場(chǎng)景?。無(wú)論是文本數(shù)據(jù)分析、關(guān)鍵詞提取、日志統(tǒng)計(jì)還是LeetCode經(jīng)典算法題型前K個(gè)高頻單詞的求解思路都是程序員必須掌握的基礎(chǔ)高階算法思維。尋常解題之法多以暴力排序遍歷雖邏輯直白卻效率堪憂而哈希表統(tǒng)計(jì)頻次 小頂堆篩選極值的組合解法兼顧時(shí)空復(fù)雜度優(yōu)勢(shì)章法嚴(yán)謹(jǐn)、思路精妙。本文將以駢文雅致之語(yǔ)層層拆解算法核心邏輯附完整C可運(yùn)行代碼、原理流程圖解、細(xì)節(jié)易錯(cuò)點(diǎn)解析帶你徹底吃透這一經(jīng)典算法。Bilibili 同步視頻力扣 692巧用小頂堆高效求解前K個(gè)高頻單詞 算法核心場(chǎng)景與解題痛點(diǎn)剖析1. 問(wèn)題場(chǎng)景定義給定一組單詞字符串?dāng)?shù)組與整數(shù)K需求為篩選出數(shù)組中出現(xiàn)頻次最高的前K個(gè)單詞排序規(guī)則嚴(yán)格遵循雙優(yōu)先級(jí) 第一優(yōu)先級(jí)單詞出現(xiàn)頻次從高到低排序 第二優(yōu)先級(jí)頻次相同時(shí)按單詞字典序從小到大排序2. 傳統(tǒng)解法弊端若采用樸素思路先遍歷統(tǒng)計(jì)所有單詞頻次再對(duì)全部單詞直接排序雖可實(shí)現(xiàn)功能卻存在顯著缺陷?數(shù)據(jù)量龐大時(shí)全局排序時(shí)間復(fù)雜度極高冗余計(jì)算過(guò)多無(wú)需對(duì)所有數(shù)據(jù)排序僅需保留前K個(gè)極值全局排序造成性能浪費(fèi)是以業(yè)界最優(yōu)解皆依托哈希表小頂堆的組合思想擇優(yōu)選取、去蕪存菁以最低時(shí)間復(fù)雜度實(shí)現(xiàn)核心需求?。?? 核心算法原理圖文拆解此番解題之術(shù)分三步行云流水、環(huán)環(huán)相扣哈希表統(tǒng)計(jì)詞頻 → 小頂堆篩選前K元素 → 結(jié)果二次規(guī)整排序?qū)訉舆f進(jìn)、邏輯閉環(huán)。1. 算法整體流程示意圖Plain Text原始單詞數(shù)組 → 哈希表遍歷統(tǒng)計(jì) → 生成【單詞-頻次】映射關(guān)系 ↓ 構(gòu)建自定義規(guī)則小頂堆 → 逐個(gè)插入單詞元素 → 堆超K則彈出最小值低頻單詞 ↓ 堆內(nèi)留存TopK高頻單詞 → 按題目雙規(guī)則二次排序 → 輸出最終有序結(jié)果2. 分步原理深度解析? 第一步哈希表遍歷精準(zhǔn)統(tǒng)計(jì)詞頻天下算法統(tǒng)計(jì)為先萬(wàn)物有序數(shù)據(jù)為基。想要篩選高頻單詞必先量化每個(gè)單詞的出現(xiàn)次數(shù)。哈希表Hash Map憑借O(1)級(jí)別的增刪查改效率成為詞頻統(tǒng)計(jì)的最優(yōu)數(shù)據(jù)結(jié)構(gòu)。我們以單詞為鍵key、出現(xiàn)頻次為值value遍歷原始單詞數(shù)組逐一對(duì)對(duì)應(yīng)單詞的頻次進(jìn)行累加最終得到所有單詞的完整頻次映射關(guān)系。此步核心要義去重統(tǒng)計(jì)、精準(zhǔn)量化將無(wú)序的原始文本數(shù)據(jù)轉(zhuǎn)化為結(jié)構(gòu)化的頻次數(shù)據(jù)為后續(xù)篩選排序筑牢根基。? 第二步自定義小頂堆篩選TopK元素求前K大極值必用小頂堆求前K小極值必用大頂堆。此為算法解題亙古不變的核心準(zhǔn)則。為何舍棄大頂堆而選用小頂堆緣由精妙小頂堆堆頂始終為當(dāng)前堆內(nèi)最小值元素遍歷插入所有單詞時(shí)若堆中元素?cái)?shù)量超出K值直接彈出堆頂?shù)皖l元素全程保留最優(yōu)的K個(gè)高頻單詞無(wú)需存儲(chǔ)全部數(shù)據(jù)極大節(jié)省內(nèi)存空間。且本題需自定義堆排序規(guī)則雙維度約束、精準(zhǔn)適配題意頻次不等頻次更高的單詞優(yōu)先級(jí)更高頻次相等字典序更小的單詞優(yōu)先級(jí)更高? 第三步二次規(guī)整排序輸出標(biāo)準(zhǔn)結(jié)果小頂堆篩選完成后堆內(nèi)元素為前K個(gè)高頻單詞但堆結(jié)構(gòu)本身無(wú)法保證全局有序。是以最后需對(duì)留存元素再次按照「頻次降序、字典序升序」的規(guī)則排序最終輸出完全符合題意的有序結(jié)果。 C 完整可運(yùn)行代碼實(shí)現(xiàn)依托上述原理結(jié)合C STL容器特性編寫(xiě)完整版高效代碼注釋詳盡、可直接編譯運(yùn)行適配各類(lèi)刷題場(chǎng)景與工程測(cè)試#includeiostream#includevector#includeunordered_map#includequeue#includealgorithmusingnamespacestd;// 自定義比較規(guī)則適配小頂堆排序邏輯structCMP{// 存儲(chǔ)單詞與對(duì)應(yīng)頻次pairstring,intval;CMP(pairstring,intv):val(v){}// 重載比較運(yùn)算符構(gòu)建符合題意的排序規(guī)則booloperator(constCMPother)const{// 頻次不同頻次低的優(yōu)先彈出小頂堆核心if(val.second!other.val.second){returnval.secondother.val.second;}// 頻次相同字典序大的優(yōu)先彈出保留字典序小的單詞returnval.firstother.val.first;}};vectorstringtopKFrequent(vectorstringwords,intk){// 1. 哈希表統(tǒng)計(jì)所有單詞頻次 O(n)unordered_mapstring,intfrequency;for(string word:words){frequency[word];}// 2. 構(gòu)建自定義小頂堆priority_queueCMPminHeap;for(autoitem:frequency){minHeap.push(CMP(item));// 堆元素超過(guò)K彈出頻次最小/字典序最大的元素if(minHeap.size()k){minHeap.pop();}}// 3. 提取堆內(nèi)結(jié)果二次規(guī)整排序vectorpairstring,inttempRes;while(!minHeap.empty()){tempRes.push_back(minHeap.top().val);minHeap.pop();}// 最終排序頻次降序同頻次字典序升序sort(tempRes.begin(),tempRes.end(),[](pairstring,inta,pairstring,intb){if(a.second!b.second){returna.secondb.second;}returna.firstb.first;});// 提取最終單詞結(jié)果vectorstringres;for(autoitem:tempRes){res.push_back(item.first);}returnres;}// 測(cè)試主函數(shù)intmain(){vectorstringtestWords{i,love,leetcode,i,love,coding};intk2;vectorstringresulttopKFrequent(testWords,k);cout前k個(gè)高頻單詞endl;for(string word:result){coutword ;}return0;}? 算法性能復(fù)雜度分析算法之優(yōu)劣必以時(shí)空復(fù)雜度為標(biāo)尺此番解法性能優(yōu)異、適配海量數(shù)據(jù)場(chǎng)景1. 時(shí)間復(fù)雜度詞頻統(tǒng)計(jì)遍歷所有單詞耗時(shí)O(n)n為單詞總數(shù)堆篩選每個(gè)元素入堆、出堆操作耗時(shí) O(logK)總耗時(shí)O(nlogK)結(jié)果排序僅對(duì)K個(gè)元素排序耗時(shí)O(KlogK)整體復(fù)雜度O(nlogK)遠(yuǎn)優(yōu)于全局排序的 O(nlogn)2. 空間復(fù)雜度哈希表存儲(chǔ)所有不重復(fù)單詞空間 O(m)m為不重復(fù)單詞數(shù)小頂堆僅存儲(chǔ)K個(gè)元素空間 O(K)整體空間復(fù)雜度O(m K)內(nèi)存占用可控、輕量化高效 拓展答疑與學(xué)習(xí)干貨1. 可否用Map替代UnorderedMap可也但非最優(yōu)?。ordered map有序map可自動(dòng)維護(hù)鍵值有序性但其底層為紅黑樹(shù)增刪查改效率低于哈希表。本題無(wú)需預(yù)處理數(shù)據(jù)有序性u(píng)nordered_map 哈希表的無(wú)序存儲(chǔ)特性更貼合高效統(tǒng)計(jì)的核心需求冗余開(kāi)銷(xiāo)更低。2. 直接全局排序可行嗎可行但低效?。全局排序依舊需要先通過(guò)哈希表統(tǒng)計(jì)詞頻并未省略核心步驟且海量數(shù)據(jù)下全局排序的時(shí)間開(kāi)銷(xiāo)遠(yuǎn)大于堆篩選數(shù)據(jù)量級(jí)越大性能差距越明顯。3. 堆排序是最優(yōu)排序算法嗎非也。在專業(yè)算法與數(shù)據(jù)結(jié)構(gòu)體系中存在多種優(yōu)于堆排序、快速排序的高階排序算法。算法學(xué)習(xí)的核心不在于死記排序模板而在于掌握?qǐng)鼍斑m配思維——按需擇取最優(yōu)解法方為算法之道。 編程學(xué)習(xí)核心感悟算法之力為思維之魂代碼之力為落地之軀。二者看似獨(dú)立實(shí)則相輔相成、共生共長(zhǎng)算法思維決定解題高度代碼功底決定落地精度。聽(tīng)課求學(xué)重在參悟解題邏輯、搭建思維框架而非拘泥于單一語(yǔ)言的代碼細(xì)節(jié)技能精進(jìn)貴在躬身實(shí)操、線下深耕而非淺嘗輒止、線上虛學(xué)。C語(yǔ)法晦澀精妙非一書(shū)可盡學(xué)需多冊(cè)典籍相輔、千行代碼沉淀方能融會(huì)貫通、運(yùn)用自如?。 總結(jié)前K個(gè)高頻單詞的解法以哈希表統(tǒng)計(jì)、小頂堆篩選、自定義排序?yàn)槿睾诵幕睘楹?jiǎn)、去冗存精。相較于暴力排序此算法極大優(yōu)化時(shí)空復(fù)雜度是極值類(lèi)算法場(chǎng)景的經(jīng)典范式。吃透此番邏輯不僅可秒殺刷題題型更能遷移應(yīng)用于文本統(tǒng)計(jì)、數(shù)據(jù)篩選、流量分析等各類(lèi)工程場(chǎng)景切實(shí)提升算法思維與代碼實(shí)戰(zhàn)能力