Sort Characters By Frequency

发表于 | 分类于

Sort Characters By Frequency

题目描述：

给定一个字符串，要求返回一个新的字符串。新的字符串所有字符和旧字符数量一样，但是排列顺序要以字符出现的顺序来排列。

例子：

具体描述见LeetCode451

解题思路：

主要思路是我们构建一个字符和字符出现次数的哈希表。而后构建一个空的桶(用vector实现)；而后遍历哈希表，根据字符出现的次数放入桶的位置，相同次数的字符放入相同的桶。最后从桶的末尾开始将字符连接即是我们要求的返回字符串。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> hash;
        string res = "";
        vector<string> bucket = {s.size() + 1, ""};
        for (auto c : s) hash[c]++;
        auto it = hash.begin();
        while(it != hash.end()){
            char c = it->first;
            int n = it->second;
            bucket[n].append(n, c);
            it++;
        }
        for (int i = bucket.size() - 1; i >= 0; i--){
            if (!bucket[i].empty()){
                res += bucket[i];
            }
        }
        return res;
    }
};