leetcode.692

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);
            }
        });

leetcode.692

巧妙的地方是维护了一个k大小的小根堆,最后翻转集合

注意点:

不熟的地方是比较器,也就是定义一个排序时的比较规则

一点感想  写了三遍之后,有了思路就很容易写下去

还有就是泛型的位置

上一篇:平行链有哪些隐藏玩法?离正式上线还有多远?| 波卡联合创始人 Robert 解密平行链


下一篇:leetcode-寻找两个正序数组的中位数