Title source

• leetcode

Title Description

title

Priority queue

• First use unordered_map Count the frequency of each letter ,key by char,value by cnt
• And then use it priority_queue The characteristics of finite queues
  • A finite queue is a large root heap by default , The big number comes first
  • pair Sort rule ： First, according to first（cnt） Sort ; If first equal , So according to second（char） Sort
• And then from priority_queue Take out the data , Press into the result string

class Solution {
    
public:
    string frequencySort(string s) {
    
        std::unordered_map<char, int> m;
        for(auto ch : s){
    
            ++m[ch];
        }

        std::priority_queue<std::pair<int, char>> q;
        for(auto it : m){
    
            q.push({
    it.second, it.first});
        }

        std::string ans;
        while (!q.empty()){
    
            auto  t = q.top(); q.pop();
            ans.append(t.first, t.second);
        }
        return ans;
    }
};

rewrite sort Of cmp

We can also use STL Self contained sort To do it , The key is to rewrite comparator, Due to the need to use external variables , Remember to put... In brackets ＆, Then we will return with high frequency , Be sure to deal with the same frequency , Otherwise, two characters with equal frequency may appear interspersed in the result res in , It's not right . See code below ：

class Solution {
    
public:
    string frequencySort(string s) {
    
        std::unordered_map<char, int> m;
        for(auto ch : s){
    
            ++m[ch];
        }

        std::sort(s.begin(), s.end(), [&](char &a, char &b){
    
            return m[a] > m[b] || (m[a] == m[b] && a < b);  //  If the frequency is the same , Put the small one in the front 
        });
        return s;
    }
};

Count sorting

We can also avoid the priority queue , Instead, create an array of strings , because A character cannot appear more than s The length of , So we put each character into the corresponding position in the array according to its occurrence times , So in the end, we just Go back and forth Array all positions , Add the string of non empty position to the result res Then you can , See code below ：

class Solution {
    
public:
    string frequencySort(string s) {
    
        std::unordered_map<char, int> m;
        for(auto ch : s){
    
            ++m[ch];
        }

        std::string ans;
        std::vector<std::string> vec(s.size() + 1);
        for(auto & a : m){
    
            vec[a.second].append(a.second, a.first);
        }
        for (int i = s.size(); i > -1; --i) {
    
            if(!vec[i].empty()){
    
                ans.append(vec[i]);
            }
        }
        return ans;
    }
};