# Top K Frequent Words

## Problem

### 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.

## 题解

### Java

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) {
if (words == null || words.length == 0) return words;
if (k <= 0) return new String[0];

Map<String, Integer> wordFreq = new HashMap<>();
for (String word : words) {
wordFreq.putIfAbsent(word, 0);
wordFreq.put(word, wordFreq.get(word) + 1);
}

PriorityQueue<KeyFreq> pq = new PriorityQueue<KeyFreq>(k);
for (Map.Entry<String, Integer> entry : wordFreq.entrySet()) {
KeyFreq kf = new KeyFreq(entry.getKey(), entry.getValue());
if (pq.size() < k) {
pq.offer(kf);
} else {
KeyFreq peek = pq.peek();
if (peek.compareTo(kf) <= 0) {
pq.poll();
pq.offer(kf);
}
}
}

int topKSize = Math.min(k, pq.size());
String[] topK = new String[topKSize];
for (int i = 0; i < k && !pq.isEmpty(); i++) {
topK[i] = pq.poll().key;
}

// reverse array
for (int i = 0, j = topKSize - 1; i < j; i++, j--) {
String temp = topK[i];
topK[i] = topK[j];
topK[j] = temp;
}

}

class KeyFreq implements Comparable<KeyFreq> {
String key;
int freq;

public KeyFreq(String key, int freq) {
this.key = key;
this.freq = freq;
}

@Override
public int compareTo(KeyFreq kf) {
if (this.freq != kf.freq) {
return this.freq - kf.freq;
}

return kf.key.compareTo(this.key);
}
}
}