451.Sort Characters By Frequency

Tags: Medium Hash Table Heap

Links: https://leetcode.com/problems/sort-characters-by-frequency/

---

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

---

class Solution {
    struct Node {
        char ch;
        int num;
        bool operator<(const Node & obj) const
        {
            return num > obj.num;
        }
    };
public:
    string frequencySort(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = s.size();
        vector<Node> count(256);
        for (auto &e : s) {
            count[e].ch = e;
            ++count[e].num;
        }
        sort(count.begin(), count.end());

        string res;
        for (int i = 0; i < 256; ++i) {
            if (!count[i].num) break;
            for (int j = 0; j < count[i].num; ++j) res.push_back(count[i].ch);
        }

        return res;
    }
};

一般涉及字符串的频率统计，都有一种通用的办法来避免使用unordeed_map，比如都是小写字母或者都是大写字母，那么都可以开一个长度为26的数组来统计频率。本题的样例解释是会存在大小写混合，并且考虑可能存在一些特殊字符比如@，那么就开一个256的数组就好了。