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.

答案

class Solution {
    /* Construct a bucket list
        index 1 contains  the list of words that appear once
        index 2 contains  the list of words that appear twice
        ...
        each list is actually a priority queue that sorts element by alphabetical order
        iterate bucket list from the larger index to smaller index, take k elements as answers 
    */
    public List<String> topKFrequent(String[] words, int k) {
        List<String> ret = new ArrayList<>();
        List<PriorityQueue<String>> bucket_list = new ArrayList<>();
        for(int i = 0; i < words.length; i++) bucket_list.add(null);

        Map<String, Integer> map = new HashMap<>();

        for(String w : words) {
            Integer freq = map.get(w);
            if(freq == null) map.put(w, 1);
            else map.put(w, freq + 1);
        }

        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            int val = entry.getValue();

            PriorityQueue<String> pq = bucket_list.get(val - 1);
            if(pq == null) {
                bucket_list.set(val - 1,  new PriorityQueue<String>());
                pq = bucket_list.get(val -1);
            }
            pq.add(key);
        }


        for(int i = bucket_list.size() - 1; i >= 0; i--) {
            PriorityQueue<String> pq = bucket_list.get(i);
            if(pq == null) continue;
            while(pq.size() > 0 && k > 0) {
                ret.add(pq.poll());
                k--;
            }
        }

        return ret;
    }
}