题意

给定字符串, 把其中字符按出现次数从大到小依次输出,其中如果两个字符出现次数相同,那么按照ascii顺序输出

限制: 字符串长度不大于1000

方法

利用C++的map/set进行统计和排序

题目既然要按照出现次数排序,那么肯定需要统计出现次数.

因此,实现分为两部分

1. 统计次数
2. 根据次数和ascii排序

对于第一部分,我们采取map来记录每个字符出现的次数

对于第二部分,考虑使用自带排序的set来进行排序

这里排序的问题是, 次数需要降序,而字符的ascii需要升序.

以题目的aaddccdc样例为例

在我们完成统计以后,得到的是

a出现2 次,c出现3次,d出现3次

如果我们按照升序排序,次数和ascii会得到

这 在次数上不满足,而在 字符上是满足的

如果我们按照降序排序,次数和ascii会得到

这 在数值上满足,而在 字符上不满足

如果 我们 让统计次数取其负数,再排升序

是满足题意的.

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    char s[1010];
    while(~scanf("%s",&s)){
        map<char,int>cnt; // 统计每个字符出现的次数
        int n = strlen(s);
        for(int i = 0;i<n;i++){
            cnt[s[i]]--; // 字符出现次数+1 (取其负数 所以是--)
        }
        set<pair<int,char>> order; // 次数从大到小, 字符从小到大
        for(auto [ch,c]:cnt){
            order.insert({c,ch}); // 先次数,后ascii
        }
        for(auto [c,ch]:order){ // 输出字符
            printf("%c",ch);
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

设不同的字符最多有$mm$个

时间复杂度: 除了读入输出,主要在排序过程中有时间消耗,所以总时间复杂度为$O(n+m\cdot log(m))O(n+m\; \backslash cdot\; log(m))$

空间复杂度: 存储两部分,一个是读入的字符串,一个是次数统计和排序,所以空间复杂度为$O(m+n)O(m+n)$

不需要实时排序,只对最后输出排序

上述过程中, 我们只需要知道最后的排序结果即可.

而set适合在一些一边排序一边需要输出的时候使用.

这里我们完全可以把所有内容都放入vector后,再一次排序.

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    char s[1010];
    while(~scanf("%s",&s)){
        map<char,int>cnt;
        int n = strlen(s);
        for(int i = 0;i<n;i++){
            cnt[s[i]]--;
        }
        vector<pair<int,char>> order;
        for(auto [ch,c]:cnt){ // 全部放入vector
            order.push_back({c,ch});
        }
        sort(order.begin(),order.end()); // 全部放入后 再排序
        for(auto [c,ch]:order){
            printf("%c",ch);
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 除了读入输出,主要在排序过程中有时间消耗,所以总时间复杂度为$O(n+m\cdot log(m))O(n+m\; \backslash cdot\; log(m))$

空间复杂度: 存储两部分,一个是读入的字符串,一个是次数统计和排序,所以空间复杂度为$O(m+n)O(m+n)$