Problem

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"],

思路一(heap)

    public String[] topKFrequentWords(String[] words, int k) {
        if (words == null || words.length == 0) {
            return new String[0];
        }
        Map<String, Integer> map = new HashMap<>();

        for (String word: words) {
            if (map.containsKey(word)) {
                map.put(word, map.get(word) + 1);
            } else {
                map.put (word, 1);
            }
        }
        MyComparator comp = new MyComparator(map);
        PriorityQueue<String> heap = new PriorityQueue<>(words.length, comp);

        for (String word: map.keySet()) {
            heap.add(word);
        }

        String[] ans = new String[k];
        for (int i = 0; i < k; i++) {
            ans[i] = heap.poll();
        }
        return ans;
    }    

class MyComparator implements Comparator<String> {
    Map<String, Integer> map;
    public MyComparator (Map<String, Integer> map) {
        this.map = map;
    }

    public int compare (String str1, String str2) {
        if (map.get(str1) != map.get(str2)) {
            return map.get(str2) - map.get(str1);
        }

        return str1.compareTo(str2);
    }
}

思路二(quick select)

• 错误, 需要按alphabetical order