网络异常，图片无法展示
|
给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
示例 1：
输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 输出: ["i", "love"] 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。 注意，按字母顺序 "i" 在 "love" 之前。 复制代码
示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4 输出: ["the", "is", "sunny", "day"] 解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词， 出现次数依次为 4, 3, 2 和 1 次。 复制代码
注意：
- 假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
- 输入的单词均由小写字母组成。
扩展练习：
- 尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。
sort 排序
本文最简单直接的方式就是统计出现的单词及其出现的次数，然后将每一个元素按照出现次数从大到小排序，如果出现次数相同，则根据字母顺序排序
最后获取降序排序后的数组的前 k 个单词即可
代码如下：
var topKFrequent = function(words, k) { // 通过map记录出现过的单词及其出现次数 const map = new Map(); for(let i = 0;i<words.length;i++){ const item = words[i]; if(map.has(item)){ map.set(item,map.get(item)+1) }else{ map.set(item,1) } } // 将每一组单词及次数存入数组 const arr = []; map.forEach((val,name) => { arr.push({name,val}) }) // 对数组排序 arr.sort((a,b) => { if(a.val===b.val) return a.name<b.name?-1:1 else return b.val-a.val }) // 获取排序后的前k个单词 const res = []; for(let i = 0;i<arr.length;i++){ if(res.length<k) res.push(arr[i].name) else break; } return res; }; 复制代码
小顶堆
涉及到维护前 k 个最值的问题，都可以通过堆来解题
本题中需要获取的是前 k 个高频单词，所以可以通过小顶堆来维护前 k 个高频单词 每次将每一组单词及次数放入堆中，最后堆中维护的就是出现频率最高的前 k 个高频单词
然后将堆中元素依次弹出放入结果数组即可
因为是小顶堆，所以堆顶是前 k 个单词中出现频率最少的一个，所以最后弹出堆顶元素插入结果数组的时候应该插入到结果数组的头部。
代码如下：
// 小顶堆 class MinHeap { constructor(k){ // 元素列表 this.arr = []; // 元素数量 this.size = 0; // 元素最大数量 this.max = k; } // 插入元素 push(item){ this.arr.push(item); this.size++; // 插入后自下向上平衡调整 if(this.size>1){ let cur = this.size-1, parent = (cur-1)>>1; while(cur>0&&compare(this.arr[parent],this.arr[cur])){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; } } // 维护堆中元素数量 if(this.size>this.max) this.pop(); } pop(){ // 弹出队中最后一个元素 if(this.size===1){ this.size = 0; return this.arr.pop(); } // 弹出堆中非最后一个元素 const res = this.arr[0]; this.arr[0] = this.arr.pop(); this.size--; // 弹出后自上向下平衡调整 let cur = 0, childl = 1,childr = 2; while( (childl<this.size&&compare(this.arr[cur],this.arr[childl])) || (childr<this.size&&compare(this.arr[cur],this.arr[childr])) ){ if(childr<this.size&&compare(this.arr[childl],this.arr[childr])){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]] cur = childl } childl = cur*2+1,childr = cur*2+2 } return res; } // 返回堆顶元素 top(){ return this.arr[0] } } // 比较两组数据方法 function compare(item1,item2){ // 出现频率相同，按字母排序 if(item1.val===item2.val) return item2.name>item1.name // 否则按出现次数排序 return item2.val<item1.val } var topKFrequent = function(words, k) { // 通过map记录出现过的单词及其出现次数 const map = new Map(); for(let i = 0;i<words.length;i++){ const item = words[i]; if(map.has(item)){ map.set(item,map.get(item)+1) }else{ map.set(item,1) } } // 创建小顶堆实例 const heap = new MinHeap(k); // 循环map，尝试将每一组数据插入堆中 map.forEach((val,name) => { const item = {name,val} // 如果堆中元素数量不够k个或者当前元素比堆顶元素大，再进行插入 if(heap.size<k||compare(item,heap.top())){ heap.push(item) } }) // 弹出堆中元素，放入结果数组 const res = []; while(heap.size){ res.unshift(heap.pop().name) } return res; }; 复制代码
至此我们就完成了 leetcode-692-前K个高频单词
如有任何问题或建议，欢迎留言讨论！
