692. 前K个高频单词


阅读量11

题目

692. 前 K 个高频单词

https://leetcode-cn.com/problems/top-k-frequent-words/

给一非空的单词列表,返回前 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, 21 次。

注意:

假定 k 总为有效值, 1 ≤ k ≤ 集合元素数。 输入的单词均由小写字母组成。

题解

思路

将字符串用哈希表存起来,再进行排序。

代码

/** * @param {string[]} words * @param {number} k * @return {string[]} */ var topKFrequent = function(words, k) { const map = new Map(); // 哈希表 words.forEach(word => { map.set(word, (map.get(word) || 0) + 1) }); const res = []; for(const key of map.keys()){ res.push(key); } // 排序 res.sort((a, b) => { return map.get(a) === map.get(b) ? a.localeCompare(b) : map.get(b) - map.get(a); }); return res.slice(0, k); };

官方

方法一:哈希表 + 排序

思路及算法

我们可以预处理出每一个单词出现的频率,然后依据每个单词出现的频率降序排序,最后返回前 kkk 个字符串即可。

具体地,我们利用哈希表记录每一个字符串出现的频率,然后将哈希表中所有字符串进行排序,排序时,如果两个字符串出现频率相同,那么我们让两字符串中字典序较小的排在前面,否则我们让出现频率较高的排在前面。最后我们只需要保留序列中的前 kkk 个字符串即可。

代码

var topKFrequent = function(words, k) { const cnt = new Map(); for (const word of words) { cnt.set(word, (cnt.get(word) || 0) + 1); } const rec = []; for (const entry of cnt.keys()) { rec.push(entry); } rec.sort((word1, word2) => { return cnt.get(word1) === cnt.get(word2) ? word1.localeCompare(word2) : cnt.get(word2) - cnt.get(word1); }) return rec.slice(0, k); };

方法二:优先队列

思路及算法

对于前 kkk 大或前 kkk 小这类问题,有一个通用的解法:优先队列。优先队列可以在 O(log⁡n)O(\log n)O(logn) 的时间内完成插入或删除元素的操作(其中 nnn 为优先队列的大小),并可以 O(1)O(1)O(1) 地查询优先队列顶端元素。

在本题中,我们可以创建一个小根优先队列(顾名思义,就是优先队列顶端元素是最小元素的优先队列)。我们将每一个字符串插入到优先队列中,如果优先队列的大小超过了 kkk,那么我们就将优先队列顶端元素弹出。这样最终优先队列中剩下的 kkk 个元素就是前 kkk 个出现次数最多的单词。

代码

class Solution { public List<String> topKFrequent(String[] words, int k) { Map<String, Integer> cnt = new HashMap<String, Integer>(); for (String word : words) { cnt.put(word, cnt.getOrDefault(word, 0) + 1); } PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(new Comparator<Map.Entry<String, Integer>>() { public int compare(Map.Entry<String, Integer> entry1, Map.Entry<String, Integer> entry2) { return entry1.getValue() == entry2.getValue() ? entry2.getKey().compareTo(entry1.getKey()) : entry1.getValue() - entry2.getValue(); } }); for (Map.Entry<String, Integer> entry : cnt.entrySet()) { pq.offer(entry); if (pq.size() > k) { pq.poll(); } } List<String> ret = new ArrayList<String>(); while (!pq.isEmpty()) { ret.add(pq.poll().getKey()); } Collections.reverse(ret); return ret; } }

czbiao 2021年5月20日 22:33 收藏文档
本站总访问量10359
本站访客数10288人次