Top K Frequent Words

 1 class Pair {
 2     String key;
 3     int value;
 4     
 5     Pair(String key, int value) {
 6         this.key = key;
 7         this.value = value;
 8     }
 9 }
10 
11 public class Solution {
12     /**
13      * @param words an array of string
14      * @param k an integer
15      * @return an array of string
16      */
17      
18     private Comparator<Pair> pairComparator = new Comparator<Pair>() {
19         public int compare(Pair left, Pair right) {
20             if (left.value != right.value) {
21                 return left.value - right.value > 0 ? 1 : -1;
22             }
23             return right.key.compareTo(left.key);
24         }
25     };
26     
27     public String[] topKFrequentWords(String[] words, int k) {
28         if (k == 0) {
29             return new String[0];
30         }
31         
32         HashMap<String, Integer> counter = new HashMap<>();
33         for (String word : words) {
34             if (counter.containsKey(word)) {
35                 counter.put(word, counter.get(word) + 1);
36             } else {
37                 counter.put(word, 1);
38             }
39         }
40         
41         PriorityQueue<Pair> Q = new PriorityQueue<Pair>(k, pairComparator);
42         for (String word : counter.keySet()) {
43             Pair peak = Q.peek();
44             Pair newPair = new Pair(word, counter.get(word));
45             if (Q.size() < k) {
46                 Q.add(newPair);
47             } else if (pairComparator.compare(newPair, peak) > 0) {
48                 Q.poll();
49                 Q.add(new Pair(word, counter.get(word)));
50             }
51         }
52         
53         String[] result = new String[k];
54         int index = 0;
55         while (!Q.isEmpty()) {
56             result[index++] = Q.poll().key;
57         }
58         for (int i = 0; i < result.length / 2; i++) {
59             String tmp = result[i];
60             result[i] = result[result.length - i - 1];
61             result[result.length - i - 1] = tmp;
62         }
63         return result;
64     }
65 }