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 <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define MAX 10000
6
7typedef struct {
8 int value;
9 int count;
10} Freq;
11
12int compare(const void *a, const void *b) {
13 return ((Freq *)b)->count - ((Freq *)a)->count;
14}
15
16int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
17 int freqMap[2 * MAX + 1] = {0};
18 Freq freqArray[numsSize];
19 int uniqueCount = 0;
20
21 for(int i = 0; i < numsSize; i++) {
22 freqMap[nums[i] + MAX]++;
23 }
24
25 for(int i = 0; i < 2 * MAX + 1; i++) {
26 if(freqMap[i]) {
27 freqArray[uniqueCount].value = i - MAX;
28 freqArray[uniqueCount].count = freqMap[i];
29 uniqueCount++;
30 }
31 }
32
33 qsort(freqArray, uniqueCount, sizeof(Freq), compare);
34
35 *returnSize = k;
36 int *result = (int*)malloc(sizeof(int) * k);
37 for(int i = 0; i < k; i++) {
38 result[i] = freqArray[i].value;
39 }
40 return result;
41}
42
43int main() {
44 int nums[] = {1, 1, 1, 2, 2, 3};
45 int k = 2;
46 int returnSize;
47 int* result = topKFrequent(nums, 6, k, &returnSize);
48 for(int i = 0; i < returnSize; i++) {
49 printf("%d ", result[i]);
50 }
51 free(result);
52 return 0;
53}
54We use a frequency map to track occurrences of each number. Then, we create a struct array for frequencies, sort it, and return 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).
1function topKFrequent(nums, k) {
2 const freqMap = {};
3 nums.forEach(num => {
4 freqMap[num] = (freqMap[num] || 0) + 1;
5 });
6
7 const buckets = Array(nums.length + 1).fill().map(() => []);
8 Object.keys(freqMap).forEach(num => {
9 buckets[freqMap[num]].push(parseInt(num));
10 });
11
12 const result = [];
13 for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
14 if (buckets[i].length > 0) {
15 result.push(...buckets[i]);
16 }
17 }
18 return result.slice(0, k);
19}
20
21const nums = [1, 1, 1, 2, 2, 3];
22const k = 2;
23console.log(topKFrequent(nums, k));
24In JavaScript, elements are counted via a map and ordered into buckets representing frequencies, making it possible to fetch the most frequent.