Formatted question description: https://leetcode.ca/all/692.html
692. Top K Frequent Words
Given a non-empty list of words, return the k most frequent elements.
Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
Input: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
Output: [“i”, “love”]
Explanation: “i” and “love” are the two most frequent words. Note that “i” comes before “love” due to a lower alphabetical order.
Input: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
Output: [“the”, “is”, “sunny”, “day”]
Explanation: “the”, “is”, “sunny” and “day” are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Input words contain only lowercase letters.
- Try to solve it in O(n log k) time and O(n) extra space.
First loop over
words and obtain each word’s number of occurrences. Use a map to store each word and its number of occurrences. Then use a priority queue to store each word and its number of occurrences, where the word with lowest number of occurrences or the highest alphabetical order is polled first. For each entry of the map, create an object from the entry and offer it into the priority queue. If the priority queue’s size is greater than k, then poll one element from the priority queue. This can make sure that there are at most k elements in the priority queue and the elements are the most frequent.
After all the words are checked, use a list to store all the words in the priority queue (in the order that they are polled from the priority queue). Then reverse the list and return.