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

发布于:2024-12-18 ⋅ 阅读:(60) ⋅ 点赞:(0)

执行结果:通过

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

 

 

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

总结

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


网站公告

今日签到

点亮在社区的每一天
去签到