Top K Frequent Words

Med Given a list of words and an integer k, return the top k frequent words in the list.

Thoughts

直观的想法，把每个str的频率统计一遍。可以维持一个大小为n的max queue，然后从中抽取k个元素.

但这样需要O(n)时间建堆，不能用一一插入建堆。

还可以维持一个大小为k的min queue, 当堆容量达到k则弹出最小的元素, O(nlgK)。

Code

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (!map.containsKey(word)) {
                map.put(word, 1);
            } else {
                map.put(word, map.get(word) + 1);
            }
        }

        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
            (a, b) -> a.getValue() == b.getValue() ? b.getKey().compareTo(a.getKey()) : a.getValue() - b.getValue()
        );
        List<String> res = new ArrayList<>();

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            pq.offer(entry);
            if(pq.size() > k) {
                pq.poll();
            }
        }

        while (!pq.isEmpty()) {
            res.add(0, pq.poll().getKey());
        }
        return res;
    }
}

Analysis

pq的size保持在k，一个n次inser/del操作，所以TC = O(nlgk)