Java实现 LeetCode 692 前K个高频单词(map的应用)
2023-09-14 08:58:02 时间
692. 前K个高频单词
给一非空的单词列表,返回前 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) 空间复杂度解决。
class Solution {
public List<String> topKFrequent(String[] words, int k) {
HashMap<String,Integer>count = new HashMap<>();
for(String word:words){
count.put(word,count.getOrDefault(word,0)+1);
}
PriorityQueue<String>heap = new PriorityQueue<String>((w1,w2)->count.get(w1).equals(count.get(w2))?w2.compareTo(w1):count.get(w1)-count.get(w2));
for(String word:count.keySet()){
heap.add(word);
if(heap.size()>k)heap.poll();
}
List<String>res = new LinkedList<>();
while(!heap.isEmpty())res.add(heap.poll());
Collections.reverse(res);
return res;
}
}
相关文章
- Java 容器 & 泛型:三、HashSet,TreeSet 和 LinkedHashSet比较
- Java实现 LeetCode 762 二进制表示中质数个计算置位(位运算+JDK的方法)
- Java实现 LeetCode 697 数组的度(类似于数组的map)
- Java实现 LeetCode 691 贴纸拼词(DFS+map记录)
- Java实现 LeetCode 652 寻找重复的子树(两个map的DFS)
- Java实现 LeetCode 638 大礼包(阅读理解题,DFS)
- Java实现 LeetCode 529 扫雷游戏(DFS)
- Java实现 LeetCode 401 二进制手表
- Java实现 LeetCode 381 O(1) 时间插入、删除和获取随机元素 - 允许重复
- Java实现 LeetCode 354 俄罗斯套娃信封问题
- Java实现 LeetCode 327 区间和的个数
- Java实现 LeetCode 215. 数组中的第K个最大元素
- Java实现 LeetCode 61 旋转链表
- Java实现 LeetCode 35 搜索插入位置
- Java实现 洛谷 P1582 倒水
- java实现 猜数字游戏
- Java实现 蓝桥杯VIP 算法提高 数字黑洞
- Java实现 蓝桥杯 算法提高 判断名次
- java parse 带英文单词的日期字符串 转 date (转化新浪微博api返回的时间)
- Atitit. 图像处理jpg图片的压缩 清理垃圾图片 java版本