LeetCode692. Top K Frequent Word

1、题目链接

https://leetcode-cn.com/problems/top-k-frequent-words/

2、解题思路

这道题的意思是说给你一个字符串数组，让你找出出现频率（出现次数）最高的前K个字母，这道题和之前做过的某一道有点类似，我们遍历数组并用Map将字符和其出现的次数存起来，然后就是挨个的找了，因为Map是无序的，所以我们需要维护一个小根堆（优先级队列），这个东西会自动帮我们排序，然后挨个的取出字符就好了，挺简单的，直接看代码：

代码

public List<String> topKFrequent(String[] words, int k) {
    List<String> result = new ArrayList<>();
    if (words != null && words.length > 0 && k > 0) {
        Map<String, Integer> map = new HashMap<>();
        // 将所有单词放进map中并记录其次数
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }
        //维护一个小根堆
        PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (map.get(o1) > map.get(o2)) {
                    return -1;
                } else if (map.get(o1) < map.get(o2)) {
                    return 1;
                } else {
                    if (o1.charAt(0) > o2.charAt(0)) {
                        return -1;
                    } else {
                        return 1;
                    }
                }
            }
        });
        // 将map中的值放到小根堆中
        for (String s : map.keySet()) {
            pq.offer(s);
        }
        // 按次数最多的取出堆中的值
        while (!pq.isEmpty() && k > 0) {
            result.add(pq.poll());
            k--;
        }
    }
    return result;
}

结果