692. 前K个高频单词

approach 1，优先队列

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String w : words) {
            map.put(w, map.getOrDefault(w, 0) + 1);
        }

        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> {
            if (map.get(a).equals(map.get(b))) {
                // 由于结果需要按字典序排列，也就是字典序小的排列在前面，所以相同计数，字典序大的排在堆顶
                return b.compareTo(a);
            }
            // 按计数排列，较小的在堆顶
            return map.get(a) - map.get(b);
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (pq.size() < k) {
                pq.offer(entry.getKey());
            } else if (entry.getValue() > map.get(pq.peek()) 
                || (entry.getValue() == map.get(pq.peek()) && entry.getKey().compareTo(pq.peek()) < 0)) {
                // 计数相同，字典序小的放入堆中，字典序相对大的从堆顶移除
                pq.poll();
                pq.offer(entry.getKey());
            }
        }

        List<String> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(pq.poll());
        }
        Collections.reverse(res);
        return res;
    }
}