class Solution {
public List<String> topKFrequent(String[] words, int k) {
//字符串键值和频率存入hashtable,都是作为比较的要素
HashMap<String,Integer> map = new HashMap();
for(String s:words)
{
if(!map.containsKey(s))
map.put(s,1);
else
map.put(s, map.get(s)+1);
}
//创建小根堆的比较器
PriorityQueue<String> minHeap = new PriorityQueue<>(new Comparator<String>(){
@Override
public int compare(String s1,String s2){
if(map.get(s1).equals(map.get(s2)))//整形的包装类型,
{
return s2.compareTo(s1);//ascil码相减的方式,返回的是一个整形
//相等的情况下谁小谁大,那就倒过来减 返回的还是正数
}
else
return map.get(s1)-map.get(s2);//不等直接返回差值
}
});
//创建小根堆,维持堆内只有我们想要的k个元素
for(String s:map.keySet())
{
minHeap.add(s);//加入在二叉树的尾部,然后堆内排序
if(minHeap.size()>k)
{
minHeap.poll();
}
}
//返回是一个list,此时次数最大的字母最小的在下面,需要翻转
List<String> list = new ArrayList();
while(minHeap.size()>0)
{
list.add(minHeap.poll());
}
//翻转集合
Collections.reverse(list);
return list;
}
}
比较器采用lambda表达式的书写
PriorityQueue<String> minHeap = new PriorityQueue<>((s1, s2) -> {
if (count.get(s1).equals(count.get(s2))) {
return s2.compareTo(s1);
} else {
return map.get(s1) - map.get(s2);
}
});
巧妙的地方是维护了一个k大小的小根堆,最后翻转集合
注意点:
不熟的地方是比较器,也就是定义一个排序时的比较规则
一点感想 写了三遍之后,有了思路就很容易写下去
还有就是泛型的位置