【LeetCode】Hash

[451] Sort Characters By Frequency [Medium]

给一个字符串，要求返回按照字母出现频率的排序后的字符串。（哈希表+桶排）

有个技巧是Hash用Value作为Index放到桶里。

class Solution {
public:
    string frequencySort(string s) {
        map<char, int> mp;
        for (auto c : s) {
            mp[c]++;
        }
        string ans = "";
        // 桶排序
        vector<string> bucket(s.size()+1, "");
        for (auto ele : mp) {
            char ch = ele.first;
            int cnt = ele.second;
            bucket[cnt].append(cnt, ch);
        }
        for (auto i = bucket.size() - 1; i >= 1; --i) {
            ans += bucket[i];
        }
        return ans;
    }
};