Link: https://leetcode.com/problems/top-k-frequent-words/
Code
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> wordFrequencyMap = new HashMap<>();
for (String w : words) {
if (!wordFrequencyMap.containsKey(w)) {
wordFrequencyMap.put(w, 1);
} else {
wordFrequencyMap.put(w, wordFrequencyMap.get(w) + 1);
}
}
PriorityQueue<Element> pq = new PriorityQueue<>((e1, e2) -> {
if (e1.count != e2.count) {
return e1.count - e2.count;
}
return e2.word.compareTo(e1.word);
});
for (String word : wordFrequencyMap.keySet()) {
Element element = new Element(word, wordFrequencyMap.get(word));
pq.offer(element);
while (pq.size() > k) {
pq.poll();
}
}
List<String> results = new LinkedList<>();
while (!pq.isEmpty()) {
Element element = pq.poll();
results.add(element.word);
}
Collections.reverse(results);
return results;
}
private class Element {
private String word;
private int count;
Element(String word, int count) {
this.word = word;
this.count = count;
}
}
}
- Time: O(nlogk).
- Space: O(n).