medium
source: https://leetcode.com/problems/top-k-frequent-elements
C/C++ Solution to LeetCode problem 347. Top K Frequent Elements.
Problem
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Examples
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints
1 <= nums.length <= 105-104 <= nums[i] <= 104kis in the range[1, the number of unique elements in the array].- It is guaranteed that the answer is unique.
Follow-up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
Solution
To solve this problem we will use a hash table to get the frequency of each number.
Then we will use a max heap, in this case a priority queue that simplifies the way to handle the max heap.
We have to sort the words by frequency (highger first).
To learn more about max heap and priority queue, see these links:
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:
typedef pair<int, int> num_freq;
struct compare {
bool operator()(num_freq& a, num_freq& b) {
return a.second > b.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> result;
unordered_map<int, int> m;
priority_queue<num_freq, vector<num_freq>, compare> pq;
for (int i=0; i<nums.size(); i+=1)
m[nums[i]] += 1;
for (auto const& [key, value]: m) {
pq.push({key, value});
if (pq.size() > k)
pq.pop();
}
while (!pq.empty()) {
result.push_back(pq.top().first);
pq.pop();
}
return result;
}
};