Top K Frequent Words
Given a non-empty list of words, return the top K frequent words in the list. The output should be sorted by frequency from highest to lowest. If two words have the same frequency, they should be sorted alphabetically.
Constraints:
- 1 <= words.length <= 10^5
- 1 <= K <= words.length
- words[i] consists of only lowercase English letters.
Examples:
Input: ["i", "love", "leetcode", "i", "love", "coding"], 3
Output: ["i", "love", "coding"]
Explanation: The words "i", "love", and "coding" have the highest frequency, and they are sorted alphabetically.
Solutions
Hash Table and Heap
Time: O(N log K)Space: O(N)
We use a hash table to count the frequency of each word, and then use a heap to sort the words by frequency and alphabetically.
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> frequency = new HashMap<>();
for (String word : words) {
frequency.put(word, frequency.getOrDefault(word, 0) + 1);
}
PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> frequency.get(b) - frequency.get(a) == 0 ? a.compareTo(b) : frequency.get(b) - frequency.get(a));
heap.addAll(frequency.keySet());
List<String> result = new ArrayList<>();
for (int i = 0;
i < k;
i++) {
result.add(heap.poll());
}
return result;
}
}Follow-up:
What if the input is a stream of words and we need to find the top K frequent words at any given time?
