LeetCode每日打卡之前K个高频单词

川长思鸟来 2023-01-23 01:58 163阅读 0赞

## 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70]

## 解题思路 ##

很明显我们先需要把所有词语出现的次数算出来。然后再根据词语的次数和词语进行排序。  
计算次数我们可以使用一个map解决，排序我们可以使用优先队列PriorityQueue。然后在PriorityQueue中保存我们需要的k个字母，并让出现次数最少的在队列的最前面，如果后续的字母出现次数比PriorityQueue队列中最前面的字母出现次数要大，则队列中最前面的字母出队，然后新字母入队。如此循环即可。实现代码如下：

public List<String> topKFrequent(String[] words, int k) { 
            Map<String, Integer> map = new HashMap<>();
            // 1. 统计所有词频
            for (String word : words) { 
                map.put(word, map.getOrDefault(word, 0) + 1);
            }
            // 2. 构建优先队列 数组下标0代表词频 数组下标1代表词语
            PriorityQueue<Object[]> queue = new PriorityQueue<>(k, (a, b) -> { 
                int c1 = (Integer) a[0], c2 = (Integer) b[0];
                //如果词频不同 根据词频升序
                if (c1 != c2) { 
                    return c1 - c2;
                }
                // 词频相同，根据词语字母排序
                String s1 = (String) a[1], s2 = (String) b[1];
                return s2.compareTo(s1);
            });
            // 如果元素小于k个直接入栈
            map.forEach((key,v) -> { 
                if (queue.size() < k) { 
                    // 注意这里key 是单词 value 是次数
                    queue.add(new Object[]{ v, key});
                } else { 
                    // 与栈顶元素比较
                    int peek = (Integer) queue.peek()[0];
                    // 词频比堆顶元素大
                    if (peek < v) { 
                    	// 栈顶元素出队
                        queue.poll();
                        // 词频大的元素入队
                        queue.add(new Object[]{ v, key});
                        //如果词频相等
                    } else if (peek == v) { 
                        String top = (String)queue.peek()[1];
                        // 且字典序大小比堆顶元素小
                        if (key.compareTo(top) < 0) { 
                        	//栈顶元素出队
                            queue.poll();
                            // 字典顺序小的元素入队
                            queue.add(new Object[]{ v, key});
                        }
                    }
                }
            });
            List<String> ans = new ArrayList<>();
            while (!queue.isEmpty()) ans.add((String)queue.poll()[1]);
            // 这里由于出栈的都是词频最低的，所以需要反转
            Collections.reverse(ans);
            return ans;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70]: /images/20221020/7097172ed8ad4302ba7c346399c800e3.png