DEV Community
·
出现频率最高的K个单词
💡
原文英文，约500词，阅读约需2分钟。
📝
内容提要
给定一个包含N个单词的数组和整数K，返回按频率从高到低排序的K个最常见单词。如果频率相同，则按字典顺序排列。使用哈希映射记录频率，并用最大堆存储单词和频率对，通过自定义比较器确保高频优先，频率相同时按字典序。时间复杂度为O(N log K)。
🎯
关键要点
-
给定一个包含N个单词的数组和整数K，返回按频率从高到低排序的K个最常见单词。
-
如果两个单词的频率相同，则按字典顺序排列。
-
使用哈希映射记录每个单词的频率。
-
使用最大堆存储单词和频率对，通过自定义比较器确保高频优先。
-
时间复杂度为O(N log K)。
-
示例输入1: 6 2，输出: i love。
-
示例输入2: 8 3，输出: is the blue。
-
代码中使用unordered_map存储单词频率，使用优先队列维护最大堆。
-
提取前K个元素以获取K个最常见的单词。
-
时间复杂度分析包括O(n)和O(n log k)。
❓
延伸问答
如何找到出现频率最高的K个单词？
通过使用哈希映射记录每个单词的频率，并利用最大堆存储单词和频率对，提取前K个元素即可。
如果两个单词的频率相同，如何处理？
如果频率相同，则按字典顺序排列，字典序较小的单词优先。
这个算法的时间复杂度是多少？
时间复杂度为O(N log K)，其中N是单词总数，K是要返回的单词数量。
如何实现最大堆来存储单词和频率对？
使用优先队列并自定义比较器，确保高频单词优先，频率相同时按字典序排列。
能否给出一个示例输入和输出？
示例输入：6 2，输出：i love；示例输入：8 3，输出：is the blue。
如何使用哈希映射记录单词频率？
遍历单词列表，首次出现的单词频率初始化为1，已存在的单词频率加1。
➡️
