题目描述
【leetcode 692. Top K Frequent Words】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.
Example 2:
Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
Output: ["the", "is", "sunny", "day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
with the number of occurrence being 4, 3, 2 and 1 respectively.Note:
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Input words contain only lowercase letters.
Follow up:
- Try to solve it in O(n log k) time and O(n) extra space.
同347 https://blog.csdn.net/orangefly0214/article/details/93034018
实现1：最小堆
//采用最小堆
public List topKFrequent(String[] words, int k) {
List ret=new LinkedList<>();
Map map=new HashMap<>();
for(String str:words){
map.put(str,map.getOrDefault(str,0)+1);
}
//声明一个最小堆
PriorityQueue pq = new PriorityQueue<>(
(a,b) -> a.getValue()==b.getValue() ? b.getKey().compareTo(a.getKey()) : a.getValue()-b.getValue()
);
//在最小堆中保留出现频率最高的2个数
for (Map.Entry entry:
map.entrySet()) {
pq.offer(entry);
if(pq.size()>k){
pq.poll();
}
}
while(!pq.isEmpty()){
ret.add(0,pq.poll().getKey());
}
return ret;
} 实现2：桶排序
//采用桶排序
public List topKFrequent2(String[] words, int k) {
HashMap map=new HashMap<>();
int max=0;
for (String w:words) {
map.put(w,map.getOrDefault(w,0)+1);
max=Math.max(max,map.get(w));
}
List[] bucket=new ArrayList[max+1];
for(Map.Entry entry:map.entrySet()){
int fre=entry.getValue();
if(bucket[fre]==null){
bucket[fre]=new ArrayList<>();
}
bucket[fre].add(entry.getKey());
}
List res=new ArrayList<>();
for (int i = max;
i>=0&&res.size()推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)