Leetcode347. 前 K 个高频元素（C语言）_c语言,前k个高频元素

Leetcode347. 前 K 个高频元素（C语言）

算法-排序（桶排序）：算法与数据结构参考

题目：
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。可假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。算法时间复杂度必须优于 O(n log n) , n 是数组的大小。例:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

思路：
哈希表存储，按出现次数排序输出。

参考力扣大佬

代码：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define Hash_SIZE 20001
#define OFFSET 10000 

typedef struct {
    int val;
    int cnt;			//cnt存储出现次数
}HashTable;
HashTable hash[Hash_SIZE];

int comp(const void *a, const void *b) {	//cnt大到小
    return (((HashTable *)b)->cnt - ((HashTable *)a)->cnt);
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    memset(hash,0,sizeof(hash));   			//初始化0
    int i,j=0;
    
    for(i=0;i<numsSize;i++){     		   //将值和出现的次数放入hash表中
        hash[(nums[i]+OFFSET)%Hash_SIZE].cnt++;   //偏移使下标>=0
        hash[(nums[i]+OFFSET)%Hash_SIZE].val=nums[i];
    }
    
    for(i=0;i<Hash_SIZE;i++){   		  //对原hash表进行优化，从开始存储
        if(hash[i].cnt!=0){
            hash[j].cnt=hash[i].cnt;
            hash[j].val=hash[i].val;
            j++;
        }
    }
    
    qsort(hash,j,sizeof(HashTable),comp);
    for(i=0;i<k;i++)	nums[i]=hash[i].val;	//输出前k个高频元素

    *returnSize=k;
    return nums;
}
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
33
34
35
36
37
38
39