Leecode刷题C语言之数组大小减半

执行结果:通过
执行用时和内存消耗如下：

 

 

1. typedef struct {
2.     int key;
3.     int val;
4.     UT_hash_handle hh;
5. } HashItem;
7. HashItem *hashFindItem(HashItem **obj, int key) {
8.     HashItem *pEntry = NULL;
9.     HASH_FIND_INT(*obj, &key, pEntry);
10.     return pEntry;
11. }
13. bool hashAddItem(HashItem **obj, int key, int val) {
14.     if (hashFindItem(obj, key)) {
15.         return false;
16.     }
17.     HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
18.     pEntry->key = key;
19.     pEntry->val = val;
20.     HASH_ADD_INT(*obj, key, pEntry);
21.     return true;
22. }
24. bool hashSetItem(HashItem **obj, int key, int val) {
25.     HashItem *pEntry = hashFindItem(obj, key);
26.     if (!pEntry) {
27.         hashAddItem(obj, key, val);
28.     } else {
29.         pEntry->val = val;
30.     }
31.     return true;
32. }
34. int hashGetItem(HashItem **obj, int key, int defaultVal) {
35.     HashItem *pEntry = hashFindItem(obj, key);
36.     if (!pEntry) {
37.         return defaultVal;
38.     }
39.     return pEntry->val;
40. }
42. void hashFree(HashItem **obj) {
43.     HashItem *curr = NULL, *tmp = NULL;
44.     HASH_ITER(hh, *obj, curr, tmp) {
45.         HASH_DEL(*obj, curr);  
46.         free(curr);
47.     }
48. }
50. static int compare(const void *a, const void *b) {
51.     return *(int *)b - *(int *)a;
52. }
54. int minSetSize(int* arr, int arrSize) {
55.     HashItem *freq = NULL;
56.     for (int i = 0; i < arrSize; i++) {
57.         hashSetItem(&freq, arr[i], hashGetItem(&freq, arr[i], 0) + 1);
58.     }
60.     int occSize = HASH_COUNT(freq);
61.     int *occ = (int *)calloc(occSize, sizeof(int));
62.     int pos = 0;
63.     for (HashItem *pEntry = freq; pEntry; pEntry = pEntry->hh.next) {
64.         occ[pos++] = pEntry->val;
65.     }
66.     qsort(occ, occSize, sizeof(int), compare);
67.     int cnt = 0, ans = 0;
68.     for (int i = 0; i < occSize; ++i) {
69.         cnt += occ[i];
70.         ans++;
71.         if (cnt * 2 >= arrSize) {
72.             break;
73.         }
74.     }
75.     hashFree(&freq);
76.     return ans;
77. }

复制代码

解题思绪：
数据结构定义

• 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，即所需的最小聚集大小，该聚集中的元素频率之和至少占数组长度的一半。
    
  
  

总结

代码实现了一个基于哈希表的功能，用于统计数组中元素的出现频率，并找到频率之和至少占数组长度一半的最小元素聚集。通过哈希表的快速查找、插入和更新操纵，以及排序算法对频率的排序，代码高效地办理了给定问题。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。