题意:
输入一个只包含小写英文字母和数字的字符串,
按照不同字符统计个数由多到少输出统计结果,如果统计的个数相同,则按照ASCII码由小到大排序输出。
方法一:
结构体快排
思路:结构体存储字符和字符的出现次数。
重写排序规则:先按照字符的出现次数降序,再按照字符的ASCII码升序。调用sort()排序。
#include <bits/stdc++.h>
using namespace std;
string s;
struct node{
int cnt;
char ch;
bool operator<(const node& x) const{//先出现次数降序,再ASCII码升序
if(cnt==x.cnt)
return ch<x.ch;
return cnt>x.cnt;
}
}a[36];
int main(){
while(cin >> s){
memset(a,0,sizeof(a));
int len=s.size();
for(int i=0;i<len;i++){//遍历字符串
if(isalpha(s[i])){//字母
a[s[i]-'a'+10].cnt++;
a[s[i]-'a'+10].ch=s[i];
}else{//数字
a[s[i]-'0'].cnt++;
a[s[i]-'0'].ch=s[i];
}
}
sort(a,a+36);//排序
for(int i=0;i<36;i++){//输出
if(a[i].cnt){
cout << a[i].ch;
}
}
cout << endl;
}
return 0;
}
时间复杂度:
空间复杂度:![]()
方法二:
计数数组
思路:
遍历一遍字符串,对字符计数并找出最大个数值。
然后,外层循环个数从大到小,内层循环ASCII码由小到大。
![]()
#include <bits/stdc++.h>
using namespace std;
string s;
unordered_map<char,int> mp;//对字符计数
char a[36];
int main(){
for(int i=0;i<10;i++)//初始化
a[i]=i+'0';
for(int i=0;i<26;i++)
a[i+10]=i+'a';
while(cin >> s){
int ma=0;//最大值
mp.clear();
int len=s.size();
for(int i=0;i<len;i++){//计数并找出最大个数值
mp[s[i]]++;
ma=max(ma,mp[s[i]]);
}
for(int i=ma;i>0;i--){//个数从大到小
for(int j=0;j<36;j++){//ASCII码由小到大
if(mp[a[j]]==i){
cout << a[j];
}
}
}
cout << endl;
}
return 0;
}
时间复杂度:
空间复杂度:![]()



京公网安备 11010502036488号