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

示例 1:

输入:
"tree"

输出:
"eert"

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

示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

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

示例 3:

输入:
"Aabb"

输出:
"bbAa"

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

Solution

参考 @liu-sha-7

// @lc code=start
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> map;
        for (char c : s){
            map[c]++;
        }
        string ss;

        while (!map.empty()) {
            char c; // 用来保存当前 map 中 value 最大的 key
            int cnt = 0; // 用来保存当前 map 中最大的 value
            // 寻找最大的键值对
            for (auto iter = map.begin(); iter != map.end(); ++iter) {
                if (iter->second > cnt) {
                    c = iter->first;
                    cnt = iter->second;
                }
            }
            // 加入到新字符串中
            while (cnt > 0) {
                ss += c;
                cnt--;
            }
            // 移除使用过的键
            map.erase(c);
        }
        return ss;
    }
};
// @lc code=end

• 利用桶排序 和 数组保存元素

class Solution {
public:
    string frequencySort(string s) {
        if (s.size() < 2) return s;

        int maxBucket = 0;
        int mp[128];  // 字符和数量的映射表
        memset(mp, 0, sizeof(int) * 128);
        for (char c : s) {
            mp[c]++;
            maxBucket = max(maxBucket, mp[c]);
        }

        vector<vector<char>> bucket(maxBucket+1);
        for (int i = 0; i < 128; ++i) {
            if (mp[i] > 0)
                bucket[mp[i]].push_back((char)i);
        }

        string ss;
        for (int i = maxBucket; i > 0; --i) {
            if (bucket[i].empty()) continue;
            for (char c : bucket[i]) {
                int cnt = i;
                while (cnt--) {
                    ss += c;
                }
            }
        }
        return ss;
    }
};