输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 输出: ["i", "love"] 解析: "i" 和 "love" 为出现次数最多的两个单词,均为2次。 注意,按字母顺序 "i" 在 "love" 之前。
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4 输出: ["the", "is", "sunny", "day"] 解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词, 出现次数依次为 4, 3, 2 和 1 次。
思路: 充分利用最小堆,里面的只能在一端删除 插入 而且栈顶为最小元素 , 最大栈不行,最大栈栈顶为最大值,不可以移除,应该保留
1 利用hashMap来统计词频 2 创建最小堆 3 最小堆插入 4 如果超过K ,移除超过部分的栈顶元素(最小的栈顶) 5 开一ArrayList来存key 6 用Collections.sort(XX,new comparator) 来进行从大到小排序, (重写 比较器) 7 返回 Arraylist
class Solution {
public List<String> topKFrequent(String[] words, int k) {
//存储
Map<String,Integer> map=new HashMap<String,Integer>();
for(String word:words){
map.put(word,map.getOrDefault(word,0)+1);
}
//创建最小堆
PriorityQueue<String> minQueue=new PriorityQueue<String>((o1,o2)->(
map.get(o1)-map.get(o2)==0?((String)o2).compareTo(((String)o1)):map.get(o1)-map.get(o2)));
//最小堆添加数据,(已经从小到大排序) 利用hashmap去除重复的key
for(String word:map.keySet()){
minQueue.add(word);
//如果size超过K,弹出堆首的数,因为最后要返回size=k的list
if(minQueue.size()>k){
minQueue.poll();
}
}
//为list赋值
List<String> list=new ArrayList<String>();
while(!minQueue.isEmpty()){
list.add(minQueue.poll());
}
//排序
Collections.sort(list,(o1,o2)->(
map.get(o1)-map.get(o2)==0?o1.compareTo(o2):map.get(o2) -map.get(o1)));
//返回结果
return list;
}
}
注意 一定要((String) o2).compareTo((String) o1) 来按字母顺序来放