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).
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define MAX 10000
6
7typedef struct FreqElem {
8 int value;
9 int count;
10} FreqElem;
11
12int compare(const void *a, const void *b) {
13 return ((FreqElem *)b)->count - ((FreqElem *)a)->count;
14}
15
16int *topKFrequent(int *nums, int numsSize, int k, int *returnSize) {
17 FreqElem buckets[numsSize + 1];
18 memset(buckets, 0, sizeof(buckets));
19
20 for (int i = 0; i < numsSize; ++i) {
21 int found = 0;
22 for (int j = 0; j < numsSize; ++j) {
23 if (buckets[j].count == 0) break;
24 if (buckets[j].value == nums[i]) {
25 buckets[j].count++;
26 found = 1;
27 break;
28 }
29 }
30 if (!found) {
31 for (int j = 0; j < numsSize; ++j) {
32 if (buckets[j].count == 0) {
33 buckets[j].value = nums[i];
34 buckets[j].count = 1;
35 break;
36 }
37 }
38 }
39 }
40
41 qsort(buckets, numsSize, sizeof(FreqElem), compare);
42
43 int *result = (int *)malloc(k * sizeof(int));
44 for (int i = 0; i < k; ++i) {
45 result[i] = buckets[i].value;
46 }
47
48 *returnSize = k;
49 return result;
50}
51
52int main() {
53 int nums[] = {1, 1, 1, 2, 2, 3};
54 int k = 2;
55 int returnSize;
56 int *result = topKFrequent(nums, 6, k, &returnSize);
57 for (int i = 0; i < returnSize; i++) {
58 printf("%d ", result[i]);
59 }
60 free(result);
61 return 0;
62}
63We manually record each element's frequency and sort the list based on counts into a frequency bucket. Then, we retrieve the top k elements.