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.

 

这道题让我们给一个字符串按照字符出现的频率来排序，那么毫无疑问肯定要先统计出每个字符出现的个数，那么之后怎么做呢？我们可以利用优先队列的自动排序的特点，把个数和字符组成pair放到优先队列里排好序后，再取出来组成结果res即可，参见代码如下：

 

解法一：

class Solution {public:    string frequencySort(string s) {        string res = "";        priority_queue
          
           
            > q;        unordered_map
            
              m;        for (char c : s) ++m[c];        for (auto a : m) q.push({a.second, a.first});        while (!q.empty()) {            auto t = q.top(); q.pop();            res.append(t.first, t.second);        }        return res;    }};
            
           
          

 

我们也可以使用STL自带的sort来做，关键就在于重写comparator，由于需要使用外部变量，记得中括号中放入＆，然后我们将频率大的返回，注意一定还要处理频率相等的情况，要不然两个频率相等的字符可能穿插着出现在结果res中，这样是不对的。参见代码如下：

 

解法二：

class Solution {public:    string frequencySort(string s) {        unordered_map
          
            m;        for (char c : s) ++m[c];        sort(s.begin(), s.end(), [&](char& a, char& b){            return m[a] > m[b] || (m[a] == m[b] && a < b);        });        return s;    }};
          

 

我们也可以不使用优先队列，而是建立一个字符串数组，因为某个字符的出现次数不可能超过s的长度，所以我们将每个字符根据其出现次数放入数组中的对应位置，那么最后我们只要从后往前遍历数组所有位置，将不为空的位置的字符串加入结果res中即可，参见代码如下：

 

解法三：

class Solution {public:    string frequencySort(string s) {        string res = "";        vector
          
            v(s.size() + 1, "");        unordered_map
           
             m;        for (char c : s) ++m[c];        for (auto& a : m) {            v[a.second].append(a.second, a.first);        }        for (int i = s.size(); i > 0; --i) {            if (!v[i].empty()) {                res.append(v[i]);            }        }        return res;    }};
           
          

 

类似题目：

 

参考资料：