692. Top K Frequent Words

Leetcode HashTable Tree Trie

Given a non-empty list of words, return the $k$ most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words.
    Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:

Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
Output: ["the", "is", "sunny", "day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
    with the number of occurrence being 4, 3, 2 and 1 respectively.

Note:

• You may assume $k$ is always valid, $1 ≤ k ≤$ number of unique elements.
• Input words contain only lowercase letters.

Follow up: Try to solve it in $O(n \log k)$ time and $O(n)$ extra space.

分析

这道题目和LeetCode 347. Top K Frequent Elements非常类似。唯一区别是前者的对象是数字，这里是字符串。所以这道题目在前者的基础上实现字符串排序即可。

public List<String> topKFrequent(String[] words, int k) {
    ArrayList<String> list = new ArrayList<>();
    if (words == null || words.length == 0 || k <= 0) return list;

    // 计算频数
    HashMap<String, Integer> map = new HashMap<>();
    for (String word : words)
        map.put(word, map.getOrDefault(word, 0) + 1);
    System.out.println(map);

    // 频数排序
    PriorityQueue<Map.Entry<String, Integer>> pq
            = new PriorityQueue<>(
                    Map.Entry.<String,Integer>comparingByValue().
                    thenComparing(Collections.reverseOrder(Map.Entry.comparingByKey())));
    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        pq.offer(entry);
        if (pq.size() > k) pq.poll();
    }

    while (!pq.isEmpty()) list.add(pq.poll().getKey());
    Collections.reverse(list);
    return list;
}

排序用lambda表达式也可以这么写

PriorityQueue<String> heap = new PriorityQueue<String>(
        (w1, w2) -> map.get(w1).equals(map.get(w2)) ?
        w2.compareTo(w1) : map.get(w1) - map.get(w2) );