执行结果:通过
执行用时和内存消耗如下:
typedef struct {
int key;
int val;
UT_hash_handle hh;
} HashItem;
HashItem *hashFindItem(HashItem **obj, int key) {
HashItem *pEntry = NULL;
HASH_FIND_INT(*obj, &key, pEntry);
return pEntry;
}
bool hashAddItem(HashItem **obj, int key, int val) {
if (hashFindItem(obj, key)) {
return false;
}
HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
pEntry->key = key;
pEntry->val = val;
HASH_ADD_INT(*obj, key, pEntry);
return true;
}
bool hashSetItem(HashItem **obj, int key, int val) {
HashItem *pEntry = hashFindItem(obj, key);
if (!pEntry) {
hashAddItem(obj, key, val);
} else {
pEntry->val = val;
}
return true;
}
int hashGetItem(HashItem **obj, int key, int defaultVal) {
HashItem *pEntry = hashFindItem(obj, key);
if (!pEntry) {
return defaultVal;
}
return pEntry->val;
}
void hashFree(HashItem **obj) {
HashItem *curr = NULL, *tmp = NULL;
HASH_ITER(hh, *obj, curr, tmp) {
HASH_DEL(*obj, curr);
free(curr);
}
}
static int compare(const void *a, const void *b) {
return *(int *)b - *(int *)a;
}
int minSetSize(int* arr, int arrSize) {
HashItem *freq = NULL;
for (int i = 0; i < arrSize; i++) {
hashSetItem(&freq, arr[i], hashGetItem(&freq, arr[i], 0) + 1);
}
int occSize = HASH_COUNT(freq);
int *occ = (int *)calloc(occSize, sizeof(int));
int pos = 0;
for (HashItem *pEntry = freq; pEntry; pEntry = pEntry->hh.next) {
occ[pos++] = pEntry->val;
}
qsort(occ, occSize, sizeof(int), compare);
int cnt = 0, ans = 0;
for (int i = 0; i < occSize; ++i) {
cnt += occ[i];
ans++;
if (cnt * 2 >= arrSize) {
break;
}
}
hashFree(&freq);
return ans;
}
解题思路:
数据结构定义
- HashItem 结构体:
- 定义一个
HashItem
结构体,包含三个字段:key
(整型,作为哈希表的键),val
(整型,存储与键相关联的值),以及UT_hash_handle hh
(由UT-hash库提供,用于内部哈希表管理)。
- 定义一个
哈希表操作函数
- hashFindItem:
- 接收一个指向哈希表头指针的指针
obj
和一个整型键key
。 - 在哈希表中查找键为
key
的项,若找到则返回该项的指针,否则返回NULL
。
- 接收一个指向哈希表头指针的指针
- hashAddItem:
- 接收一个指向哈希表头指针的指针
obj
、一个整型键key
和一个整型值val
。 - 首先检查键
key
是否已存在于哈希表中,若存在则不添加并返回false
。 - 若不存在,则为新项分配内存,设置其键和值,并将其添加到哈希表中,最后返回
true
。
- 接收一个指向哈希表头指针的指针
- hashSetItem:
- 接收一个指向哈希表头指针的指针
obj
、一个整型键key
和一个整型值val
。 - 在哈希表中查找键为
key
的项,若找到则更新其值为val
。 - 若未找到,则调用
hashAddItem
函数添加新项。 - 函数始终返回
true
。
- 接收一个指向哈希表头指针的指针
- hashGetItem:
- 接收一个指向哈希表头指针的指针
obj
、一个整型键key
和一个默认整型值defaultVal
。 - 在哈希表中查找键为
key
的项,若找到则返回其值,否则返回defaultVal
。
- 接收一个指向哈希表头指针的指针
- hashFree:
- 接收一个指向哈希表头指针的指针
obj
。 - 遍历哈希表,删除每个项并释放其内存。
- 接收一个指向哈希表头指针的指针
辅助函数
- compare:
- 用于
qsort
函数进行整型数组的降序排序。
- 用于
主要函数
- minSetSize:
- 接收一个整型数组
arr
和其大小arrSize
。 - 使用哈希表
freq
统计数组中每个元素的出现频率。 - 遍历哈希表,将每个元素的频率存储到整型数组
occ
中。 - 对
occ
数组进行降序排序。 - 初始化计数器
cnt
和答案ans
,遍历排序后的occ
数组,累加频率到cnt
,同时递增ans
。 - 当
cnt
的两倍大于或等于数组arr
的大小时,停止遍历。 - 释放哈希表
freq
占用的内存。 - 返回
ans
,即所需的最小集合大小,该集合中的元素频率之和至少占数组长度的一半。
- 接收一个整型数组
总结
代码实现了一个基于哈希表的功能,用于统计数组中元素的出现频率,并找到频率之和至少占数组长度一半的最小元素集合。通过哈希表的快速查找、插入和更新操作,以及排序算法对频率的排序,代码高效地解决了给定问题。