【leetcode】692. 前K个高频单词

 

public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        // 通过map将每个元素出现的次数给统计出来,key是元素本身,value是元素出现的次数
        for (String word : words) {
            if (map.get(word)!=null){
                map.put(word,map.get(word)+1);
            }else{
                map.put(word,1);
            }
        }
        /**
         * 通过 java的 PriorityQueue实现一个小根堆
         * 堆中存放元素的逻辑
         * 1. 按照元素出现的次数由小到大排序(下面的else分支)因为这样可以保证在当前堆中,堆顶放的元素出现的次数是最小的
         *    如果下次有新元素到来,且新元素的次数比堆顶元素的大,则用新元素替换堆中元素次数最小的那个(也就是堆顶元素)
         * 2. 在堆中,如果两个元素的次数相同,则按照元素的字母顺序从大到小排序
         *    比如 "aaa" 和 "a" 二者都出现一次,这时应该按照字母顺序从大到小排序,这样可以保证字母顺序大的更靠近堆顶
         *    如果新元素的次数比 1大,那么被替换的就是 "aaa" (if分支)
         */
        PriorityQueue<Map.Entry<String,Integer>> priorityQueue = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue() == o2.getValue()){
                    return o2.getKey().compareTo(o1.getKey());
                }else{
                    return o1.getValue()-o2.getValue();
                }
            }
        });
        /**
         * 将元素放入到priorityQueue的两种情况
         * 1. priorityQueue的size未满(比k小),则直接将元素放进 priorityQueue (if分支)
         * 2. priorityQueue元素等于k,这时应该拿出堆顶元素和新到元素进行比较,比较规则有两个
         *    1). 如果新到元素出现的次数比堆顶元素的大,则直接移除堆顶元素,将新到元素放入堆中(else分支中的if判断的第一个条件)
         *    2). 如果新到元素出现的次数和堆顶元素的一样,则比较新到元素和堆顶元素的字母顺序,如果新到元素的字母顺序比堆顶元素的小,则移除堆顶元素,放入新到元素
         */
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (priorityQueue.size()<k){
                priorityQueue.add(entry);
            }else{
                Map.Entry<String, Integer> peek = priorityQueue.peek();
                if ((entry.getValue()>peek.getValue()) ||
                        ((entry.getValue() == peek.getValue())
                                && (peek.getKey().compareTo(entry.getKey())>0))){
                    priorityQueue.remove();
                    priorityQueue.add(entry);
                }
            }
        }
        // 因为 priorityQueue 实现的是小根堆,且堆内元素按字母顺序由小到大排序,因此刚好和题目要求的顺序反过来
        List<String> results = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            results.add(priorityQueue.poll().getKey());
        }
        // 偷懒,直接用集合的翻转方法(如果这一步自己实现的话,可以考虑用栈)
        Collections.reverse(results);
       return results;
    }

 

【leetcode】692. 前K个高频单词

上一篇:Macbook M1芯片录制屏幕声音


下一篇:html 学习笔记