• 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;
}

算法逻辑说明

  1. 核心思路

    • 通过两层嵌套循环枚举每个字符的出现次数
    • 外层循环遍历每个字符作为"当前比较字符"
    • 内层循环统计该字符在整个字符串中的出现次数
    • 每次统计后更新最大次数和对应字符
  2. 关键处理逻辑

    • 初始化策略:将MaxSizeChar设为'z'(ASCII码较大),确保首次遇到字符时一定能更新
    • 次数比较:当新字符次数更大时,直接更新最大值;次数相同时,保留ASCII码更小的字符
    • 字符比较:利用C++中字符的ASCII码自然顺序(如'a' < 'b' < ... < 'z')进行比较
  3. 时间复杂度

    • 两层循环均遍历字符串所有字符,时间复杂度为O(n²),其中n为字符串长度
    • 对于题目限制(长度≤1000),该复杂度在合理范围内

示例运行过程(以输入"abbccc"为例)

  1. 初始状态MaxSize=0MaxSizeChar='z'
  2. i=0,字符'a'
    • 内层循环统计'a'出现1次(cnt=1)
    • 1 > 0,更新MaxSize=1MaxSizeChar='a'
  3. i=1,字符'b'
    • 统计'b'出现2次(cnt=2)
    • 2 > 1,更新MaxSize=2MaxSizeChar='b'
  4. i=2,字符'b'
    • 统计结果仍为2次(cnt=2)
    • 次数等于当前最大值,比较ASCII码:'b'不小于当前MaxSizeChar('b'),不更新
  5. i=3,字符'c'
    • 统计'c'出现3次(cnt=3)
    • 3 > 2,更新MaxSize=3MaxSizeChar='c'
  6. i=4,字符'c'
    • 统计结果为3次,ASCII码'c'不小于当前值,不更新
  7. i=5,字符'c'
    • 统计结果为3次,同样不更新
  8. 循环结束:输出c 3,与样例结果一致

优化建议

该算法虽然实现了功能,但存在重复统计问题(如多次统计同一个字符)。优化方向:

  • 使用数组统计字符频率(如int count[26] = {0}),只需O(n)时间完成统计
  • 减少嵌套循环,将时间复杂度从O(n²)优化到O(n)
  • 示例优化代码可参考之前回答中的"统计字符数"问题解法

2 条评论

  • @ 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;
    }
    

    核心算法说明

    1. 桶统计原理

      • 使用全局数组ascii,下标为字符的ASCII码值,数组值为对应字符的出现次数
      • 例如:字符'a'(ASCII码97)对应ascii[97]'b'对应ascii[98],以此类推
    2. 函数逻辑

      • cntSize函数接收字符串引用作为参数,避免拷贝开销
      • 首次遍历字符串时填充"桶数组",二次遍历桶数组找出最大值
      • 利用ASCII码的有序性,自然实现"次数相同则选ASCII码最小字符"的要求
    3. 全局变量应用

      • ascii数组作为全局变量,在函数间共享数据
      • 主函数直接通过ascii[maxchar]获取最大次数,无需额外返回值

    示例运行过程(输入"abbccc")

    1. 初始化ascii数组所有元素为0
    2. 遍历字符串统计
      • 字符'a'(ASCII 97):ascii[97] = 1
      • 字符'b'(ASCII 98):ascii[98] = 2
      • 字符'c'(ASCII 99):ascii[99] = 3
    3. 查找最大值
      • 遍历i=0~127时,ascii[99]=3为最大值,MaxChar='c'
    4. 主函数输出c 3,符合样例要求

    存在的问题与优化建议

    1. 潜在问题

      • 全局数组未在每次调用后重置,若多次运行程序会累积统计结果
      • 数组大小定义为200,实际只需覆盖ASCII码范围(0~127),可优化为ascii[128]
    2. 优化方向

      • cntSize函数开始处添加memset(ascii, 0, sizeof(ascii));重置数组
      • 将全局数组改为局部数组或类成员,避免全局变量污染
      • 针对题目限定的a-z字符,可缩小数组范围为ascii[26],下标对应'a'-'z'
    3. 修正后的函数开头

      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