根据字符出现频率排序

这类问题主要用到lambda排序

import collections
m=collections.Counter(s)
m=sorted(m.items(),key=lambda x: -x[1])

map<char, int> mm; // 统计频次
for (auto &i:s) {
    mm[i] += 1;
}
vector<pair<char,int>> v(mm.begin(), mm.end());
sort(v.begin(),v.end(),[](pair<char,int>&a,pair<char,int>&b){
    return a.second>b.second; // 按值逆序排序
});

451. 根据字符出现频率排序

• 统计s的频次并存入字典
• 将字典转成向量，并把该向量按值的逆序排序
• 根据排好序的向量，按键和值生成每个子字符串，并将其加到res结果中

class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        import collections
        m=collections.Counter(s)
        m=sorted(m.items(),key=lambda x: -x[1])
        res=""
        for i in m:
            tmp=i[0]*i[1]
            res+=tmp
        ## 或者
        # for k,v in m:
        #     tmp=k*v;
        #     res+=tmp
        return res

字典转向量，然后排序

class Solution {
public:
    string frequencySort(string s) {
        map<char, int> mm; // 统计频次
        for (auto &i:s) {
            mm[i] += 1;
        }
        vector<pair<char,int>> v(mm.begin(), mm.end());
        sort(v.begin(),v.end(),[](pair<char,int>&a,pair<char,int>&b){
            return a.second>b.second; // 按值逆序排序
        });
        string res="";
        for (int i = 0; i < v.size(); ++i) {
            string tmp(v[i].second,v[i].first); // 按键和值，生成每个子字符串
            res+=tmp;
        }
        return res;
    }
};

另一种写法：字典转成multimap，multimap可以自动按键升序排序

class Solution {
public:
    string frequencySort(string s) {
        map<char, int> mm; // 统计频次
        for (auto &i:s) {
            mm[i] += 1;
        }
        multimap<int,char>multim; // 键和值互相调换，multimap自动按键的升序排列
        for(auto [c,i]:mm){
            multim.insert({i,c});
        }
        string res="";
        for(multimap<int,char>::iterator it=multim.begin(); it!=multim.end();++it){
            string tmp(it->first,it->second);
            res+=tmp; // 拼接字符串
        }
        reverse(res.begin(), res.end()); // 反转
        return res;
    }
};

347. 前 K 个高频元素

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> mm; // 统计频次
        for (auto &i:nums) {
            mm[i] += 1;
        }
        vector<pair<int,int>> v(mm.begin(), mm.end());
        sort(v.begin(),v.end(),[](pair<int,int>&a,pair<int,int>&b){
            return a.second>b.second; // 按值逆序排序
        });
        vector<int>res;
        for (int i = 0; i < k; ++i) {
            res.push_back(v[i].first);
        }
        return res;
    }
};

692. 前K个高频单词

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> mm; // 统计频次
        for (auto &i:words) {
            mm[i] += 1;
        }
        vector<pair<string,int>> v(mm.begin(), mm.end());
        sort(v.begin(),v.end(),[](pair<string,int>&a,pair<string,int>&b){
            if (a.second==b.second){
                return a.first<b.first;
            }
            return a.second>b.second; // 按值逆序排序
        });
        vector<string>res;
        for (int i = 0; i < k; ++i) {
            res.push_back(v[i].first);
        }
        return res;
    }
};