leetcode 451. Sort Characters By Frequency 排序即可

阳光穿透心脏的1/2处 2022-06-04 08:37 145阅读 0赞

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.

题意很简单，就是一个简单的排序，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    
    using namespace std;
    
    
    bool cmp(pair<char, int> a , pair<char, int> b)
    {
        return a.second > b.second;
    }
    class Solution 
    {
    public:
        string frequencySort(string s) 
        {
            map<char, int> mmp;
            for (char a : s)
            {
                if (mmp.find(a) == mmp.end())
                    mmp[a] = 1;
                else
                    mmp[a] += 1;
            }
            vector<pair<char, int>> res(mmp.begin(),mmp.end());
            sort(res.begin(), res.end(), cmp);
    
            string tmp = "";
            for (pair<char, int> a : res)
            {
                for (int i = 0; i < a.second; i++)
                    tmp += a.first;
            }
            return tmp;
        }
    };