leetcode451. 根据字符出现频率排序

• 1. 题目
• 2. 解答

1. 题目

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:
输入:
“tree”
输出:
“eert”

解释:
'e’出现两次，'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。

示例 2:
输入:
“cccaaa”
输出:
“cccaaa”

解释:
'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:
输入:
“Aabb”
输出:
“bbAa”

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意’A’和’a’被认为是两种不同的字符。

2. 解答

typedef struct {
    int key;
    int count;
    UT_hash_handle hh;
} HashTable;

int cmp(const void *a, const void *b)
{
    HashTable *s1 = (HashTable *)a;
    HashTable *s2 = (HashTable *)b;
    return s2->count - s1->count;
}

char * frequencySort(char * s) {
    HashTable *g_str = NULL;
    int len = strlen(s);

    for (int i = 0; i < len; i++) {
        HashTable *find = NULL;
        int var = s[i];       // 注意此处要用个变量接一下，否则直接调用HASH_FIND_INT(g_str, &s[i], find);会出现段错误
        HASH_FIND_INT(g_str, &var, find);
        if (find != NULL) {
            find->count++;
        } else {
            HashTable *cur = (HashTable *)malloc(sizeof(HashTable));
            cur->key = var;
            cur->count = 1;
            HASH_ADD_INT(g_str, key, cur);
        }
    }

    HASH_SORT(g_str, cmp);

    char *res = (char *)malloc(sizeof(char) * (len + 1));
    int index = 0;
    HashTable *cur = NULL;
    HashTable *next = NULL;
    HASH_ITER(hh, g_str, cur, next) {
        for (int i = 0; i < cur->count; i++) {
            res[index++] = cur->key;
        }
    }
    res[index] = '\0';
    return res;
}