This approach uses a hash map to count the frequency of each element. We then use a min-heap to keep track of the top k elements.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing frequencies.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <queue>
5
6using namespace std;
7
8vector<int> topKFrequent(vector<int>& nums, int k) {
9 unordered_map<int, int> freqMap;
10 for (int num : nums) {
11 freqMap[num]++;
12 }
13
14 auto compare = [&](int a, int b) { return freqMap[a] > freqMap[b]; };
15 priority_queue<int, vector<int>, decltype(compare)> minHeap(compare);
16
17 for (auto& p : freqMap) {
18 minHeap.push(p.first);
19 if (minHeap.size() > k) {
20 minHeap.pop();
21 }
22 }
23
24 vector<int> result;
25 while (!minHeap.empty()) {
26 result.push_back(minHeap.top());
27 minHeap.pop();
28 }
29 return result;
30}
31
32int main() {
33 vector<int> nums = {1, 1, 1, 2, 2, 3};
34 int k = 2;
35 vector<int> result = topKFrequent(nums, k);
36 for (int num : result) {
37 cout << num << " ";
38 }
39 return 0;
40}
41We use a hash map to count frequencies, then use a min-heap of size k to keep track of the top k elements.
This approach involves using bucket sort where we create buckets for frequency counts and then extract the top k frequent elements.
Time Complexity: O(n + k).
Space Complexity: O(n).
1from collections import Counter
2
3def topKFrequent(nums, k):
4 count = Counter(nums)
5 buckets = [[] for _ in range(len(nums) + 1)]
6
7 for num, freq in count.items():
8 buckets[freq].append(num)
9
10 result = []
11 for i in range(len(buckets) - 1, 0, -1):
12 for num in buckets[i]:
13 result.append(num)
14 if len(result) == k:
15 return result
16
17if __name__ == '__main__':
18 nums = [1, 1, 1, 2, 2, 3]
19 k = 2
20 print(topKFrequent(nums, k))
21Even with Python, we leverage frequency count with buckets to directly access and collect top k frequent elements.