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

执行结果:通过

执行用时和内存消耗如下：

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;
}

解题思路：

数据结构定义

1. HashItem 结构体：
   • 定义一个 HashItem 结构体，包含三个字段：key（整型，作为哈希表的键），val（整型，存储与键相关联的值），以及 UT_hash_handle hh（由UT-hash库提供，用于内部哈希表管理）。

哈希表操作函数

1. hashFindItem：
   • 接收一个指向哈希表头指针的指针 obj 和一个整型键 key。
   • 在哈希表中查找键为 key 的项，若找到则返回该项的指针，否则返回 NULL。
2. hashAddItem：
   • 接收一个指向哈希表头指针的指针 obj、一个整型键 key 和一个整型值 val。
   • 首先检查键 key 是否已存在于哈希表中，若存在则不添加并返回 false。
   • 若不存在，则为新项分配内存，设置其键和值，并将其添加到哈希表中，最后返回 true。
3. hashSetItem：
   • 接收一个指向哈希表头指针的指针 obj、一个整型键 key 和一个整型值 val。
   • 在哈希表中查找键为 key 的项，若找到则更新其值为 val。
   • 若未找到，则调用 hashAddItem 函数添加新项。
   • 函数始终返回 true。
4. hashGetItem：
   • 接收一个指向哈希表头指针的指针 obj、一个整型键 key 和一个默认整型值 defaultVal。
   • 在哈希表中查找键为 key 的项，若找到则返回其值，否则返回 defaultVal。
5. hashFree：
   • 接收一个指向哈希表头指针的指针 obj。
   • 遍历哈希表，删除每个项并释放其内存。

辅助函数

1. compare：
   • 用于 qsort 函数进行整型数组的降序排序。

主要函数

1. minSetSize：
   • 接收一个整型数组 arr 和其大小 arrSize。
   • 使用哈希表 freq 统计数组中每个元素的出现频率。
   • 遍历哈希表，将每个元素的频率存储到整型数组 occ 中。
   • 对 occ 数组进行降序排序。
   • 初始化计数器 cnt 和答案 ans，遍历排序后的 occ 数组，累加频率到 cnt，同时递增 ans。
   • 当 cnt 的两倍大于或等于数组 arr 的大小时，停止遍历。
   • 释放哈希表 freq 占用的内存。
   • 返回 ans，即所需的最小集合大小，该集合中的元素频率之和至少占数组长度的一半。

总结

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