题解
最有面儿的字符
1 条题解
-
0
解题思路
题目说"出现次数最多的字符最有面儿";如果好几个字符出现次数一样多、并且都最多,就选 ASCII 码最小的那个(也就是字母表里最靠前的字母)。
做法:
- 因为字符串里只可能有 'a'~'z' 这26个字母,我们准备一个长度为26的数组
cnt。cnt[0]~cnt[25]分别记录 'a'~'z' 出现的次数。 - 统计每个字母的次数。 遍历字符串,每看到一个字符
s[i],就把cnt[s[i]-'a']加1。这里的s[i]-'a'是一个小技巧:'a'-'a'=0,'b'-'a'=1,……,'z'-'a'=25,正好得到"它是第几个字母"。 - 找答案。 用一个变量
mx记住"次数最多的字母的下标"。从下标0开始往25走,只有当cnt[i]严格大于cnt[mx]时才更新mx。这样做的妙处是:如果两个字母次数一样多,我们会保留更靠前(下标更小)的那一个——比如 t 和 y 都出现2次,我们保留 t,正好满足"ASCII码最小"。 - 输出字母(
'a'+mx)和它的次数(cnt[mx]),中间用空格分开。
参考代码
// 最有面儿的字符:找出现次数最多、ASCII码最小的那个字母 #include <iostream> #include <string> using namespace std; int cnt[26]; // cnt[0]~cnt[25]分别记'a'~'z'出现的次数 int main(){ string s; cin>>s; for(int i=0;i<s.size();i++) cnt[s[i]-'a']++; // 统计每个字母出现的次数 int mx=0; // 从'a'开始往'z'找,用 > 判断:次数相同(ASCII码更小)的不会被替换,保证最小 for(int i=1;i<26;i++) if(cnt[i]>cnt[mx]) mx=i; cout<<(char)('a'+mx)<<" "<<cnt[mx]<<'\n'; return 0; }复杂度分析
- 时间复杂度:O(L),L 是字符串长度(不超过1000)。我们只需要把字符串从头到尾扫一遍。
- 空间复杂度:O(1)。虽然用了一个
cnt数组,但它固定只有26个格子,和字符串长度无关,所以是常数空间。
- 因为字符串里只可能有 'a'~'z' 这26个字母,我们准备一个长度为26的数组
- 1