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.
def topKFrequent(words, k):
frequency = {}
for word in words:
frequency[word] = frequency.get(word, 0) + 1
return sorted(frequency, key=lambda x:
(-frequency[x], x))[:k]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?
