- C++
1.13编程基础之综合应用 29:统计字符数
- 2025-5-28 18:59:24 @
程序功能与结构解析
这个程序的功能是统计输入字符串中出现次数最多的字符,若有多个字符出现次数相同且最多,则输出ASCII码最小的那个字符。以下是详细的代码注释与解析:
#include<iostream>
using namespace std;
int main() {
// 读取输入的字符串
string ss;
cin >> ss;
// 获取字符串长度
int len = ss.size();
// 初始化最大值变量:MaxSize记录最大出现次数,MaxSizeChar记录对应字符(初始为'z',确保能被更小字符更新)
int MaxSize = 0;
char MaxSizeChar = 'z';
// 外层循环:遍历字符串中的每个字符作为当前比较字符
for(int i = 0; i < len; i++) {
// 初始化当前字符的计数器
int cnt = 0;
// 记录当前遍历的字符
char tempChar = ss[i];
// 内层循环:统计当前字符在整个字符串中的出现次数
for(int j = 0; j < len; j++) {
if(ss[i] == ss[j]) {
cnt += 1; // 若字符相同,计数器加1
}
}
// 比较当前字符的出现次数与最大值
if(cnt > MaxSize) {
// 若当前次数更大,则更新最大次数和对应字符
MaxSize = cnt;
MaxSizeChar = tempChar;
} else if(cnt == MaxSize) {
// 若次数相同,比较ASCII码,保留更小的字符
if(tempChar < MaxSizeChar) {
MaxSizeChar = tempChar;
}
}
}
// 输出结果:最大次数的字符及其出现次数
cout << MaxSizeChar << " " << MaxSize;
return 0;
}
算法逻辑说明
-
核心思路:
- 通过两层嵌套循环枚举每个字符的出现次数
- 外层循环遍历每个字符作为"当前比较字符"
- 内层循环统计该字符在整个字符串中的出现次数
- 每次统计后更新最大次数和对应字符
-
关键处理逻辑:
- 初始化策略:将
MaxSizeChar
设为'z'(ASCII码较大),确保首次遇到字符时一定能更新 - 次数比较:当新字符次数更大时,直接更新最大值;次数相同时,保留ASCII码更小的字符
- 字符比较:利用C++中字符的ASCII码自然顺序(如'a' < 'b' < ... < 'z')进行比较
- 初始化策略:将
-
时间复杂度:
- 两层循环均遍历字符串所有字符,时间复杂度为O(n²),其中n为字符串长度
- 对于题目限制(长度≤1000),该复杂度在合理范围内
示例运行过程(以输入"abbccc"为例)
- 初始状态:
MaxSize=0
,MaxSizeChar='z'
- i=0,字符'a':
- 内层循环统计'a'出现1次(cnt=1)
- 1 > 0,更新
MaxSize=1
,MaxSizeChar='a'
- i=1,字符'b':
- 统计'b'出现2次(cnt=2)
- 2 > 1,更新
MaxSize=2
,MaxSizeChar='b'
- i=2,字符'b':
- 统计结果仍为2次(cnt=2)
- 次数等于当前最大值,比较ASCII码:'b'不小于当前
MaxSizeChar('b')
,不更新
- i=3,字符'c':
- 统计'c'出现3次(cnt=3)
- 3 > 2,更新
MaxSize=3
,MaxSizeChar='c'
- i=4,字符'c':
- 统计结果为3次,ASCII码'c'不小于当前值,不更新
- i=5,字符'c':
- 统计结果为3次,同样不更新
- 循环结束:输出
c 3
,与样例结果一致
优化建议
该算法虽然实现了功能,但存在重复统计问题(如多次统计同一个字符)。优化方向:
- 使用数组统计字符频率(如
int count[26] = {0}
),只需O(n)时间完成统计 - 减少嵌套循环,将时间复杂度从O(n²)优化到O(n)
- 示例优化代码可参考之前回答中的"统计字符数"问题解法
2 条评论
-
admin SU @ 2025-5-28 19:50:09
代码功能与结构解析
这个程序通过"桶排序"思想统计字符串中出现次数最多的字符,以下是详细的代码注释与解析:
#include<iostream> using namespace std; // 定义全局数组作为"桶",用于统计字符出现次数(ASCII码范围0~127) int ascii[200] = {}; // 数组所有元素初始化为0 // 函数功能:计算出现次数最多的字符(返回该字符) char cntSize(const string& ss) { int len = ss.size(); // 获取字符串长度 // 遍历字符串,统计每个字符的出现次数 for(int i = 0; i < len; i++) { ascii[ss[i]] += 1; // 将字符的ASCII码作为数组下标,对应位置计数加1 } int Max = 0; // 记录最大出现次数 char MaxChar; // 记录出现次数最多的字符 // 遍历所有ASCII码范围,找出出现次数最多的字符 for(int i = 0; i <= 127; i++) { if(ascii[i] > Max) { // 发现更大的出现次数 Max = ascii[i]; MaxChar = char(i); // 将ASCII码转换为字符 } } return MaxChar; // 返回出现次数最多的字符 } int main() { string ss; cin >> ss; // 读取输入字符串 char maxchar = cntSize(ss); // 调用函数获取出现次数最多的字符 // 输出结果:字符及其出现次数(通过全局数组直接获取次数) cout << maxchar << " " << ascii[maxchar] << endl; return 0; }
核心算法说明
-
桶统计原理:
- 使用全局数组
ascii
,下标为字符的ASCII码值,数组值为对应字符的出现次数 - 例如:字符
'a'
(ASCII码97)对应ascii[97]
,'b'
对应ascii[98]
,以此类推
- 使用全局数组
-
函数逻辑:
cntSize
函数接收字符串引用作为参数,避免拷贝开销- 首次遍历字符串时填充"桶数组",二次遍历桶数组找出最大值
- 利用ASCII码的有序性,自然实现"次数相同则选ASCII码最小字符"的要求
-
全局变量应用:
ascii
数组作为全局变量,在函数间共享数据- 主函数直接通过
ascii[maxchar]
获取最大次数,无需额外返回值
示例运行过程(输入"abbccc")
- 初始化:
ascii
数组所有元素为0 - 遍历字符串统计:
- 字符
'a'
(ASCII 97):ascii[97] = 1
- 字符
'b'
(ASCII 98):ascii[98] = 2
- 字符
'c'
(ASCII 99):ascii[99] = 3
- 字符
- 查找最大值:
- 遍历
i=0~127
时,ascii[99]=3
为最大值,MaxChar='c'
- 遍历
- 主函数输出:
c 3
,符合样例要求
存在的问题与优化建议
-
潜在问题:
- 全局数组未在每次调用后重置,若多次运行程序会累积统计结果
- 数组大小定义为200,实际只需覆盖ASCII码范围(0~127),可优化为
ascii[128]
-
优化方向:
- 在
cntSize
函数开始处添加memset(ascii, 0, sizeof(ascii));
重置数组 - 将全局数组改为局部数组或类成员,避免全局变量污染
- 针对题目限定的
a-z
字符,可缩小数组范围为ascii[26]
,下标对应'a'-'z'
- 在
-
修正后的函数开头:
char cntSize(const string& ss) { memset(ascii, 0, sizeof(ascii)); // 重置数组为0 int len = ss.size(); // 后续代码不变... }
-
-
2025-5-28 19:49:59@
http://noi.openjudge.cn/ch0113/29/
OpenJudge test 信箱 账号 题目ID, 标题, 描述
NOI NOI / 1.13编程基础之综合应用 题目 排名 状态 提问 29:统计字符数 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 给定一个由a-z这26个字符组成的字符串,统计其中哪个字符出现的次数最多。
输入 输入包含一行,一个字符串,长度不超过1000。 输出 输出一行,包括出现次数最多的字符和该字符出现的次数,中间以一个空格分开。如果有多个字符出现的次数相同且最多,那么输出ascii码最小的那一个字符。 样例输入 abbccc 样例输出 c 3 来源 1744
- 1