力扣 692：巧用小顶堆高效求解前K个高频单词

力扣 692巧用小顶堆高效求解前K个高频单词 前言Bilibili 同步视频 算法核心场景与解题痛点剖析1. 问题场景定义2. 传统解法弊端⚙️ 核心算法原理图文拆解1. 算法整体流程示意图Plain Text2. 分步原理深度解析✅ 第一步哈希表遍历精准统计词频✅ 第二步自定义小顶堆筛选TopK元素✅ 第三步二次规整排序输出标准结果 C 完整可运行代码实现⚡ 算法性能复杂度分析1. 时间复杂度2. 空间复杂度 拓展答疑与学习干货1. 可否用Map替代UnorderedMap2. 直接全局排序可行吗3. 堆排序是最优排序算法吗 编程学习核心感悟 总结 前言在算法刷题与工程开发之中词频统计、高频元素筛选是极为经典的核心场景✨。无论是文本数据分析、关键词提取、日志统计还是LeetCode经典算法题型前K个高频单词的求解思路都是程序员必须掌握的基础高阶算法思维。寻常解题之法多以暴力排序遍历虽逻辑直白却效率堪忧而哈希表统计频次 小顶堆筛选极值的组合解法兼顾时空复杂度优势章法严谨、思路精妙。本文将以骈文雅致之语层层拆解算法核心逻辑附完整C可运行代码、原理流程图解、细节易错点解析带你彻底吃透这一经典算法。Bilibili 同步视频力扣 692巧用小顶堆高效求解前K个高频单词 算法核心场景与解题痛点剖析1. 问题场景定义给定一组单词字符串数组与整数K需求为筛选出数组中出现频次最高的前K个单词排序规则严格遵循双优先级 第一优先级单词出现频次从高到低排序 第二优先级频次相同时按单词字典序从小到大排序2. 传统解法弊端若采用朴素思路先遍历统计所有单词频次再对全部单词直接排序虽可实现功能却存在显著缺陷❌数据量庞大时全局排序时间复杂度极高冗余计算过多无需对所有数据排序仅需保留前K个极值全局排序造成性能浪费是以业界最优解皆依托哈希表小顶堆的组合思想择优选取、去芜存菁以最低时间复杂度实现核心需求✅。⚙️ 核心算法原理图文拆解此番解题之术分三步行云流水、环环相扣哈希表统计词频 → 小顶堆筛选前K元素 → 结果二次规整排序层层递进、逻辑闭环。1. 算法整体流程示意图Plain Text原始单词数组 → 哈希表遍历统计 → 生成【单词-频次】映射关系 ↓ 构建自定义规则小顶堆 → 逐个插入单词元素 → 堆超K则弹出最小值低频单词 ↓ 堆内留存TopK高频单词 → 按题目双规则二次排序 → 输出最终有序结果2. 分步原理深度解析✅ 第一步哈希表遍历精准统计词频天下算法统计为先万物有序数据为基。想要筛选高频单词必先量化每个单词的出现次数。哈希表Hash Map凭借O(1)级别的增删查改效率成为词频统计的最优数据结构。我们以单词为键key、出现频次为值value遍历原始单词数组逐一对对应单词的频次进行累加最终得到所有单词的完整频次映射关系。此步核心要义去重统计、精准量化将无序的原始文本数据转化为结构化的频次数据为后续筛选排序筑牢根基。✅ 第二步自定义小顶堆筛选TopK元素求前K大极值必用小顶堆求前K小极值必用大顶堆。此为算法解题亘古不变的核心准则。为何舍弃大顶堆而选用小顶堆缘由精妙小顶堆堆顶始终为当前堆内最小值元素遍历插入所有单词时若堆中元素数量超出K值直接弹出堆顶低频元素全程保留最优的K个高频单词无需存储全部数据极大节省内存空间。且本题需自定义堆排序规则双维度约束、精准适配题意频次不等频次更高的单词优先级更高频次相等字典序更小的单词优先级更高✅ 第三步二次规整排序输出标准结果小顶堆筛选完成后堆内元素为前K个高频单词但堆结构本身无法保证全局有序。是以最后需对留存元素再次按照「频次降序、字典序升序」的规则排序最终输出完全符合题意的有序结果。 C 完整可运行代码实现依托上述原理结合C STL容器特性编写完整版高效代码注释详尽、可直接编译运行适配各类刷题场景与工程测试#includeiostream#includevector#includeunordered_map#includequeue#includealgorithmusingnamespacestd;// 自定义比较规则适配小顶堆排序逻辑structCMP{// 存储单词与对应频次pairstring,intval;CMP(pairstring,intv):val(v){}// 重载比较运算符构建符合题意的排序规则booloperator(constCMPother)const{// 频次不同频次低的优先弹出小顶堆核心if(val.second!other.val.second){returnval.secondother.val.second;}// 频次相同字典序大的优先弹出保留字典序小的单词returnval.firstother.val.first;}};vectorstringtopKFrequent(vectorstringwords,intk){// 1. 哈希表统计所有单词频次 O(n)unordered_mapstring,intfrequency;for(string word:words){frequency[word];}// 2. 构建自定义小顶堆priority_queueCMPminHeap;for(autoitem:frequency){minHeap.push(CMP(item));// 堆元素超过K弹出频次最小/字典序最大的元素if(minHeap.size()k){minHeap.pop();}}// 3. 提取堆内结果二次规整排序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;});// 提取最终单词结果vectorstringres;for(autoitem:tempRes){res.push_back(item.first);}returnres;}// 测试主函数intmain(){vectorstringtestWords{i,love,leetcode,i,love,coding};intk2;vectorstringresulttopKFrequent(testWords,k);cout前k个高频单词endl;for(string word:result){coutword ;}return0;}⚡ 算法性能复杂度分析算法之优劣必以时空复杂度为标尺此番解法性能优异、适配海量数据场景1. 时间复杂度词频统计遍历所有单词耗时O(n)n为单词总数堆筛选每个元素入堆、出堆操作耗时 O(logK)总耗时O(nlogK)结果排序仅对K个元素排序耗时O(KlogK)整体复杂度O(nlogK)远优于全局排序的 O(nlogn)2. 空间复杂度哈希表存储所有不重复单词空间 O(m)m为不重复单词数小顶堆仅存储K个元素空间 O(K)整体空间复杂度O(m K)内存占用可控、轻量化高效 拓展答疑与学习干货1. 可否用Map替代UnorderedMap可也但非最优✨。ordered map有序map可自动维护键值有序性但其底层为红黑树增删查改效率低于哈希表。本题无需预处理数据有序性unordered_map 哈希表的无序存储特性更贴合高效统计的核心需求冗余开销更低。2. 直接全局排序可行吗可行但低效❌。全局排序依旧需要先通过哈希表统计词频并未省略核心步骤且海量数据下全局排序的时间开销远大于堆筛选数据量级越大性能差距越明显。3. 堆排序是最优排序算法吗非也。在专业算法与数据结构体系中存在多种优于堆排序、快速排序的高阶排序算法。算法学习的核心不在于死记排序模板而在于掌握场景适配思维——按需择取最优解法方为算法之道。 编程学习核心感悟算法之力为思维之魂代码之力为落地之躯。二者看似独立实则相辅相成、共生共长算法思维决定解题高度代码功底决定落地精度。听课求学重在参悟解题逻辑、搭建思维框架而非拘泥于单一语言的代码细节技能精进贵在躬身实操、线下深耕而非浅尝辄止、线上虚学。C语法晦涩精妙非一书可尽学需多册典籍相辅、千行代码沉淀方能融会贯通、运用自如✨。 总结前K个高频单词的解法以哈希表统计、小顶堆筛选、自定义排序为三重核心化繁为简、去冗存精。相较于暴力排序此算法极大优化时空复杂度是极值类算法场景的经典范式。吃透此番逻辑不仅可秒杀刷题题型更能迁移应用于文本统计、数据筛选、流量分析等各类工程场景切实提升算法思维与代码实战能力