Top K Frequent Elements
Given an integer array nums and an integer k, return the top k frequent elements in the array.
Constraints:
- 1 <= nums.length <= 10^5
- 1 <= k <= 10^5
- It is guaranteed that the answer is unique.
Examples:
Input: [1,1,1,2,2,3] and k = 2
Output: [1,2]
Explanation: The elements 1 and 2 are the top 2 frequent elements in the array.
Solutions
Hash Table and Heap
Time: O(N log k)Space: O(N)
We use a hash table to count the frequency of each element in the array. Then we use a max heap to find the top k frequent elements.
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> count;
for (int num : nums) {
count[num]++;
}
priority_queue<pair<int, int>> maxHeap;
for (auto& entry : count) {
maxHeap.push({
entry.second, entry.first}
);
}
vector<int> result;
for (int i = 0;
i < k;
i++) {
result.push_back(maxHeap.top().second);
maxHeap.pop();
}
return result;
}
}
;Follow-up:
What if the input array is very large and does not fit into memory?
