链接：https://leetcode.cn/problems/sort-array-by-increasing-frequency/solution/-by-xun-ge-v-6eu0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

C语言对于hash有一个很好用的库C语言哈希算法详解，建议去看看

本题就是对上述库的一个简单运用

我们以nums[i]的值为键创建哈希表，遍历数组将数组中元素加入哈希表，加入之前查询当前数值是否在哈希表中存在，如果存在就将其计数+1，不存在则创建哈希节点。最后对哈希表中元素进行排序，最后从头遍历哈希表中元素并将其加入数组中输出即可

建议结合代码食用，代码注释超级详细

代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

struct my_struct {//哈希结构
    int val;            /* we'll use this field as the key */
    int count;
    UT_hash_handle hh; /* makes this structure hashable */
};
//排序，先按出现次数排序，如果相同则排序大小
int by_count(const struct my_struct *a, const struct my_struct *b) {
    return a->count == b->count ? (b->val - a->val) : (a->count - b->count);
}

int* frequencySort(int* nums, int numsSize, int* returnSize){
    struct my_struct *users = NULL; //定义哈希表头
    struct my_struct *s = NULL;//定义哈希表节点
    for(int i = 0; i < numsSize; i++)//遍历数组
    {
        HASH_FIND_INT(users, &nums[i], s);//查询是否在哈希表中出现
        if(s)//出现过，计算+1
        {
            s->count++;
        }
        else//没有出现过，添加进哈希表
        {
            s = (struct my_struct*)malloc(sizeof *s);
            s->val = nums[i];
            s->count = 1;
            HASH_ADD_INT(users, val, s); //添加宏
        }
    }

    HASH_SORT(users, by_count);//排序宏

    *returnSize = 0;
    for (s = users; s != NULL; s = s->hh.next) {//遍历哈希表中每一个元素
        while(s->count--)//存入数组
        {
            nums[(*returnSize)++] = s->val;
        }
    }
    //销毁哈希表
    struct my_struct *current_user, *tmp;
    HASH_ITER(hh, users, current_user, tmp) {
        HASH_DEL(users, current_user);  /* delete; users advances to next */
        free(current_user);             /* optional- if you want to free  */
    }


    return nums;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/sort-array-by-increasing-frequency/solution/-by-xun-ge-v-6eu0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。