[数据结构与算法]力扣692(前K个高频单词)

力扣692(前k个高频单词)

题干

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例

思路

第一步:统计每个单词出现的次数(使用map)

第二步:使用topK思想将键值对进行topK式存储,之所以要存储键值对,是因为,同次数的单词需要比较字典序的先后来判断谁去谁留,这里有个较容易失误的点:由于是找前k个value值最大的键值对,那按道理是要建立一个小根堆,但有个特殊情况:就是value值相同时:字典序更靠后的更有可能被挤出topK,所以对这种情况:需要将字典序更靠后的键值对放在相对更靠近堆顶的位置,也即对这种情况建立大根堆!除此之外的情况,就按照value值建立正常的小根堆即可.

第三步:将topK个元素逐一输出即可,这样输出的结果是单词出现次数从小到大输出的,所以使用了java的一个集合Collections的内置方法,将输出结果进行了逆置

代码

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        if(words==null) return null;
        //topK问题,找最大的若干个键值对,所以建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> pri=new PriorityQueue<>(k,new Comparator<Map.Entry<String,Integer>>(){
            public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
                //如果次数相同,要将字典序更大的字符串放在更靠近堆顶的位置
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }else{
                    return o1.getValue().compareTo(o2.getValue());
                }
            }
        });
        //先将键值对打包放进map中,说白了把每个字符串出现的次数都统计一下
        Map<String,Integer> map=new HashMap<>();
        for(int i=0;i<words.length;i++){
            if(map.get(words[i])==null){
                map.put(words[i],1);
            }else{
                int oldValue=map.get(words[i]);
                map.put(words[i],oldValue+1);
            }
        }
        //使用topK思想解决问题
        Set<Map.Entry<String,Integer>> entries=map.entrySet();
        for(Map.Entry<String,Integer> tmp:entries){
            if(pri.size()<k){
                pri.offer(tmp);
            }else{
                Map.Entry<String,Integer> front=pri.peek();
                if(front.getValue().compareTo(tmp.getValue())==0){
                    if(front.getKey().compareTo(tmp.getKey())>0){
                        pri.poll();
                        pri.offer(tmp);
                    }
                }else{
                    if(front.getValue().compareTo(tmp.getValue())<0){
                        pri.poll();
                        pri.offer(tmp);
                    }
                }
            }
        }
        //现在topK已经处理完毕,按照题干输出即可
        List<String> list=new ArrayList<>();
        for(int i=0;i<k;i++){
            Map.Entry<String,Integer> front=pri.poll();
            list.add(front.getKey());
        }

        Collections.reverse(list);

        return list;
    }
}