leetcode347.前k个高频元素

leetcode347.前k个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]

优先队列法

struct hash_table {int key;int val;UT_hash_handle hh;
};//表示一个哈希表条目,包含key和val字段。
//定义一个指向hash_table结构的指针。
typedef struct hash_table* hash_ptr;struct pair {int first;int second;
};//表示一对整数。struct pair* heap;//用作堆的整数对数组。
int heapSize;//堆的大小的变量。void swap(struct pair* a, struct pair* b) {struct pair t = *a;*a = *b, *b = t;
}bool cmp(struct pair* a, struct pair* b) {return a->second < b->second;
}struct pair top() {//返回堆顶元素。return heap[1];
}int push(hash_ptr x) {//将新元素推入堆并维护堆属性。heap[++heapSize].first = x->key;heap[heapSize].second = x->val;int p = heapSize, s;while (p > 1) {s = p >> 1;if (cmp(&heap[s], &heap[p])) return 0;swap(&heap[p], &heap[s]);p = s;}return 1;
}int pop() {heap[1] = heap[heapSize--];int p = 1, s;while ((p << 1) <= heapSize) {s = p << 1;if (s < heapSize && cmp(&heap[s + 1], &heap[s])) s++;if (cmp(&heap[p], &heap[s])) return 0;swap(&heap[p], &heap[s]);p = s;}return 1;
}int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {hash_ptr head = NULL;hash_ptr p = NULL, tmp = NULL;for (int i = 0; i < numsSize; i++) {//遍历数组，计算每个元素出现频率，并将其存储在哈希表中HASH_FIND_INT(head, &nums[i], p);if (p == NULL) {p = malloc(sizeof(struct hash_table));p->key = nums[i];p->val = 1;HASH_ADD_INT(head, key, p);} else {p->val++;}}//堆初始化heap = malloc(sizeof(struct pair) * (k + 1));heapSize = 0;/*如果堆的元素个数等于 k，则检查堆顶与当前出现次数的大小。如果堆顶更大(小根堆堆顶元素为最小值），说明至少有 k个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。*//*HASH_ITER(hh, head, p, tmp) {//查找前k个频繁元素if (heapSize == k) {//堆已满(大小 == k)struct pair tmp = top();if (tmp.second < p->val) {//将堆顶元素与当前元素进行比较pop();//当前元素的频率更高,它会替换堆顶元素。push(p);//将p推入堆中}} else {push(p);//堆大小不等于k直接入栈}}/*它从堆中检索顶部元素并将其存储在临时变量 tmp 中。它从堆中弹出顶部元素。它将 tmp 的第一个值赋给数组 ret 的第 i 个元素。*//**returnSize = k;int* ret = malloc(sizeof(int) * k);for (int i = k-1; i >=0; i--) {//逆序输出堆元素struct pair tmp = top();pop();ret[i] = tmp.first;}return ret;
}

暴力法

#include <stdio.h>
#include <stdlib.h>// 结构体用于存储元素和其出现的频率
typedef struct {int num;int freq;
} Element;// 比较函数，用于qsort排序
int compare(const void *a, const void *b) {return ((Element *)b)->freq - ((Element *)a)->freq;
}int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {// 统计每个元素的频率Element *elements = (Element *)malloc(numsSize * sizeof(Element));int count = 0;for (int i = 0; i < numsSize; i++) {int j;for (j = 0; j < count; j++) {if (elements[j].num == nums[i]) {elements[j].freq++;break;}}if (j == count) {elements[count].num = nums[i];elements[count].freq = 1;count++;}}// 对元素按频率进行排序qsort(elements, count, sizeof(Element), compare);// 返回前k个高频元素int *result = (int *)malloc(k * sizeof(int));*returnSize = k;for (int i = 0; i < k; i++) {result[i] = elements[i].num;}free(elements);return result;
}