力扣-根据字符出现频率排序

ohye / 2023-08-24 / 原文

1.问题描述

给定一个字符串，请将字符串里的字符按照出现的频率降序排列，如果频率相同，则按照字符的ASCII码升序排列。

示例 1:

输入:

"tree"

输出:

"eert"

解释:

'e'出现两次，'r'和't'都只出现一次。

因此'e'必须出现在'r'和't'之前，而且'r'比't'的ASCII码小。

示例 2:

输入:

"cccaaa"

输出:

"aaaccc"

解释:

'c'和'a'都出现三次。因此按照字符升序排列，'a'在'c'前。

示例 3:

输入:

"Aabb"

输出:

"bbAa"

解释:

'A'和'a'被认为是两种不同的字符，并且'A'的ASCII码比'a'小

2.说明

输入：输入一个字符串

输出：

输出一个字符串，字符串中字符的顺序请参考以上说明。

3.范例

输入：Aabb

输出：bbAa

4.思路

使用哈希表，统计字符出现的频率，然后将字符去重后存入列表，再将列表中的字符按照频率降序排序，根据题目要求，字符出现频率相同时，使用SACII升序排列，因此排序时需要注意，最后对于每个字符，将该字符按照出现频率拼接到排序后的字符串。

5.代码

#include <iostream>
#include <string>
#include <stdio.h>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

class Solution
{
public:
    string charSort(string s)
    {
        map<char,int> map_s;
        for(int i=0;i<s.length();i++)
        {
            map_s[s[i]]++;
        }
        vector<pair<char,int> > vec;
        for(auto &it:map_s)
            vec.emplace_back(it);
        sort(vec.begin(),vec.end(),[](const pair<char,int>&a,const pair<char,int> &b)
             {
                 if(a.second==b.second) return a.first<b.first;
                 else return a.second>b.second;
             });
        string result;
        for(int i=0;i<vec.size();i++)
        {
            char ch=vec[i].first;
            int num=vec[i].second;
            for(int i=0;i<num;i++)
                result.push_back(ch);
        }
        return result;
    }
};
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    Solution solve;
    string s;
    cin>>s;
    string result=solve.charSort(s);
    cout<<result<<endl;
    return 0;
}