题意:
输入一个只包含小写英文字母和数字的字符串,
按照不同字符统计个数由多到少输出统计结果,如果统计的个数相同,则按照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; }
时间复杂度:空间复杂度: