淄博网站制作网页优化,个性定制网站,wordpress可视化编辑失效,网站做优化按点击收费leetcode347.前k个高频元素
给你一个整数数组 nums 和一个整数 k #xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2]
示例 2: 输入: nums [1], k 1 输出: [1]
优先队列法
struct hash_…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;
}
