Leetcode692 Top-K Frequent Words

Posted on

题目

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:

1
2
3
4
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:

1
2
3
4
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.

解析

经典的问题，寻找topk频率的单词，如果遇到tie则比较字典序，字典序小的在前面，遍历一边统计顺序，利用heap或者说priority queue保存即可，不过记录这道题的目的是用下java 对函数编程的支持，因为以前都是新建一个class做的，比较笨拙

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<String> topKFrequent(String[] words, int k) {
    List<String> res = new LinkedList<>();
    Map<String, Integer> count = new HashMap<>();
    for(String word: words){
        count.put(word, count.getOrDefault(word,0) + 1);
    }
    // 这边可以向pq传递一个比较参数，为lambda表达式
    // 有一个比较trick的是通过三目运算来解决tie的问题，相当于实现了一个if else语句
    PriorityQueue<String> pq = new PriorityQueue<>((a,b) -> count.get(a).equals(count.get(b)) ? b.compareTo(a) : count.get(a) - count.get(b));
    for(String word: count.keySet()){
        pq.add(word);
        if(pq.size() > k)
            pq.poll();
    }
    while(!pq.isEmpty()){
        res.add(pq.poll());
    }

    //注意此时的res是反的，题目要求返回从高频到低频的单词
    Collections.reverse(res);
    return res;
}

总结

topk这种高频入门必刷题，需要熟练掌握，用一些函数式编程的小trick可以让我们做题速度更快，代码更加优雅