Top K Frequent Words Problem
Description
LeetCode Problem 692.
Given an array of strings words and an integer k, return the k most frequent strings.
Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.
Example 1:
1
2
3
4
Input: words = ["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.
Example 2:
1
2
3
Input: words = ["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.
Constraints:
- 1 <= words.length <= 500
- 1 <= words[i] <= 10
- words[i] consists of lowercase English letters.
- k is in the range [1, The number of unique words[i]] Follow-up: Could you solve it in O(n log(k)) time and O(n) extra space?
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int> hashmap;
for (string& word : words) {
hashmap[word] += 1;
}
priority_queue<pair<int, string>, vector<pair<int, string>>, MyComp> pq;
for (auto it = hashmap.begin(); it != hashmap.end(); ++it) {
pq.push(make_pair(it->second, it->first));
if (pq.size() > k)
pq.pop();
}
vector<string> res;
while (!pq.empty()) {
res.insert(res.begin(), pq.top().second);
pq.pop();
}
return res;
}
private:
struct MyComp {
bool operator() (const pair<int, string>& a, const pair<int, string>& b) {
if (a.first != b.first) {
return a.first > b.first;
}
else {
return a.second < b.second;
}
}
};
};