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.
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int> frequency;
for (const string& word : words) {
frequency[word]++;
}
priority_queue<pair<int, string>> heap;
for (const auto& pair : frequency) {
heap.push({
pair.second, pair.first}
);
}
vector<string> result;
for (int i = 0;
i < k;
i++) {
result.push_back(heap.top().second);
heap.pop();
}
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?
