[LintCode] 471 Top K Frequent Words 解题报告

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


Notice
You should order the words by the frequency of them in the return list, the most frequent one comes first. If two words has the same frequency, the one with lower alphabetical order come first.


Example
Given

[
    "yes", "lint", "code",
    "yes", "code", "baby",
    "you", "baby", "chrome",
    "safari", "lint", "code",
    "body", "lint", "code"
]
for k = 3, return ["code", "lint", "baby"].

for k = 4, return ["code", "lint", "baby", "yes"],



Challenge
Do it in O(nlogk) time and O(n) extra space.

Extra points if you can do it in O(n) time with O(k) extra space approximation algorithms.



思路
先用HashMap统计一下每一个word的频率。
建立一个min-heap，把HashMap里的Pair以频率排序，往heap里扔。
heap超过k就用poll扔掉一个回到k的size。
最后把heap里剩下的k个倒出来。



Code

class Pair {
    String word;
    int freq;
    public Pair(String word, int freq) {
        this.word = word;
        this.freq = freq;
    }
}

public class Solution {
    /**
     * @param words an array of string
     * @param k an integer
     * @return an array of string
     */
    public String[] topKFrequentWords(String[] words, int k) {
        // Write your code here
        
        if (k == 0) {
            return new String[0];
        }
        
        HashMap<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);
            }
        }
        
        Queue<Pair> heap = new PriorityQueue<Pair>(k, new Comparator<Pair>() {
            public int compare(Pair x, Pair y) {
                if (x.freq != y.freq) {
                    return x.freq - y.freq;
                }
                return y.word.compareTo(x.word);
            }
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            
            Pair p = new Pair(entry.getKey(), entry.getValue());
            
            heap.offer(p);
            
            if (heap.size() > k) {
                heap.poll();
            }
        }
        
        String[] result = new String[k];
        while (!heap.isEmpty()) {
            Pair p = heap.poll();
            result[--k] = p.word;
        }
        
        return result;
    }
}