[leetcode]692.|[leetcode]692. Top K Frequent Words 最高频K个单词
Given a non-empty list of words, return the k most frequent elements.
Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
Example 1:
Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 Output: ["i", "love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order
题目
思路
1. Using HashMap and PriorityQueue
2. Build a HashMap to get the word frequency
3. PriorityQueue (minHeap) - if the counts are same return higher lexicographically word first so that the lower remains in the queue
4. We add each entry to PQ. If the PQ size > k, then we pop the lowest value in the PQ.
跟[leetcode]347. Top K Frequent Elements K个最常见元素思路完全一致
代码
1 /* 2 Time: O(nlogk) 3 Space: O(n) 4 */ 5 6 class Solution { 7public List topKFrequent(String[] words, int k) { 8List result = new LinkedList<>(); 9// freq map 10Map map = new HashMap<>(); 11for(String s: words){ 12map.put(s, map.containsKey(s) ? map.get(s) + 1 : 1); 13} 14// b.getKey().compareTo(a.getKey()) 处理了频率相同,按字典顺序排列的题意要求 15PriorityQueueminHeap = new PriorityQueue<>( 16(a,b) -> a.getValue()==b.getValue() ? b.getKey().compareTo(a.getKey()) : a.getValue()-b.getValue() 17); 18 19for(Map.Entry entry: map.entrySet()) 20{ 21minHeap.offer(entry); 22if(minHeap.size()>k) 23// 自定义从小到大的顺序保证了poll出来的是较小值,留在minHeap里的是较大值 24minHeap.poll(); 25} 26 27while(!minHeap.isEmpty()) 28result.add(0, minHeap.poll().getKey()); 29 30return result; 31} 32 }
【[leetcode]692.|[leetcode]692. Top K Frequent Words 最高频K个单词】转载于:https://www.cnblogs.com/liuliu5151/p/9824013.html
推荐阅读
- parallels|parallels desktop 解决网络初始化失败问题
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- LintCode|LintCode 545 [Top k Largest Number II]
- BNC公链|BNC公链 | Eth2.0测试网Topaz已质押超100万枚ETH
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- LeetCode(03)Longest|LeetCode(03)Longest Substring Without Repeating Characters
- 前端代码|前端代码 返回顶部 backToTop
- 程序员客栈TOP收入的萌系开发者心得|程序员客栈TOP收入的萌系开发者心得 - 雨晴