题目描述

出现次数最多的k个数 Top K Frequent Words。

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.

思路

(堆)
题解：因为题目要求是O(nlogk)的时间复杂度，所以不能用排序方法做，可以使用堆结构来解决问题。首先可以使用一个hash表统计出每个单词出现的次数，然后我们使用一个容量为K的堆（大顶堆序）存储所有map中的Key，Value, 然后循环k次取出堆顶元素, 得到的答案就是结果了。

Java代码

public class Solution {

    private Map<String, Integer> map = null;
    private PriorityQueue<Map.Entry<String, Integer>> pq = null;
    private List<String> res = null;

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

        res = new ArrayList<>();
        map = new HashMap<>(n);
        // max heap
        // 1. compare Map.Entry value
        // 2. if same, then sort by Map.Entry key
        // 3. if not same, sort by Map.Entry value
        pq = new PriorityQueue<>((a, b) -> a.getValue().equals(b.getValue()) ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue());

        // counting every word
        for (int i = 0; i < n; i++) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }

        // addAll to pq
        pq.addAll(map.entrySet());

        // get top k
        for (int i = 0; i < k; i++) {
            Optional.ofNullable(pq.poll()).ifPresent(e -> res.add(e.getKey()));
        }

        return res;
    }
}

时间复杂度 O(nlogk)