杨校老师课堂之字符桶排序算法——桶排序结合字符标记专项题单

原创

杨校

发布于 2025-07-03 14:25:30

9700

代码可运行

文章被收录于专栏：C++信息学奥赛C++信息学奥赛

运行总次数：0

代码可运行

一、知识重点

（一）字符桶的本质：数组映射字符

核心逻辑：用数组下标映射字符的 ASCII 值，数组元素存储字符出现的次数（或是否出现）。

字符 → 下标：利用字符的 ASCII 码（如 'a' 的 ASCII 是 97，'A' 是 65 ），直接作为数组下标。
次数 → 元素值：数组元素值记录该字符出现的次数（或标记是否出现）。

（二）字符桶的 3 大典型应用场景

1. 统计每个字符的出现次数（字符的统计） 2. 找出现次数最多的字符（字符的计数）

3. 找未出现的字符（字符的存在）

（三）字符桶的关键知识点

知识点	说明
数组与 ASCII 的映射	利用字符的 ASCII 码作为数组下标，实现 “字符→次数” 的直接映射
桶数组的初始化	需覆盖目标字符的 ASCII 范围（如小写字母 97-122，大写字母 65-90）
遍历与筛选逻辑	通过循环遍历桶数组，结合条件判断（>0/==0/>maxx）筛选结果
字符与整数的转换	输出时用 (char)i 将 ASCII 值转回字符；输入时 char c 直接存 ASCII 值

（四）字符桶的扩展与进阶

支持更多字符：
- 若涉及中文或特殊字符，需用 ** Unicode 编码 **（如 wchar_t 或字符串统计），但基础思想一致（用下标映射编码值）。
优化空间使用：
- 针对小写字母（26 个），可压缩数组大小为 int a[26]，用 c - 'a' 映射下标（如 a[c-'a']++ ），更节省空间。
处理复杂需求：
- 多条件筛选（如同时统计大小写、排除特殊字符）
- 结合排序输出（如按出现次数排序，而非 ASCII 顺序）

二、专项训练

1. 字符的统计

【题目描述】

输入n个字符，输出每个字符出现次数，保证字符都是小写字母。

【输入格式】

输入共两行，第一行一个整数n(n<1000) 第二行包括n个字符，字符之间由空格隔开。

【输出格式】

输出若干行，每行为出现的字符及字符出现的次数，中间用空格隔开。

【输入样例】

6

a b b c c c

【输出样例】

a 1

b 2

c 3

#include<iostream>
using namespace std;

int main() {
    int n;  // 用于存储输入的字符个数
    int a[125] = {0};  // 定义一个大小为125的整型数组a并初始化为0，用于统计字符出现的次数
    char c;  // 用于存储输入的字符

    cin >> n;  // 从标准输入读取字符的个数

    // 循环n次，输入字符并统计出现次数
    for(int i = 1; i <= n; ++i) {  
        cin >> c;  // 从标准输入读取一个字符
        ++a[c];  // 将数组a中下标为字符c的ASCII值的元素值加1
    }

    // 输出ASCII值在97到122（小写字母a-z）之间且出现次数不为0的字符及其出现次数
    for(int i = 97; i <= 122; ++i) {  
        if(a[i]!= 0)  // 如果该字符出现过
            cout << (char)i << " " << a[i] << endl;  // 输出字符及其出现次数，并换行
    }

    return 0;  
}

2. 字符的计数

【题目描述】

计算n个字符中出现次数最多的字符，保证字符都是小写字母。

【输入格式】

输入共两行，第一行一个整数n(n<1000)，第二行包括n个字符，字符之间由空格隔开。

【输出格式】

输出一行，包括出现次数最多的字符和该字符出现的次数，中间以一个空格分开。如果有多个字符出现的次数相同且最多，那么输出ASCII码最小的那一个字符。

【输入样例】

6

a b b c c c

【输出样例】

c 3

#include<iostream>
using namespace std;

int main() {
    int n;  // 用于存储输入的字符个数
    int a[125] = {0};  // 定义一个大小为125的整型数组a并初始化为0，用于统计字符出现的次数
    char c;  // 用于存储输入的字符

    cin >> n;  // 从标准输入读取字符的个数

    // 循环n次，输入字符并统计出现次数
    for(int i = 1; i <= n; ++i) {  
        cin >> c;  // 从标准输入读取一个字符
        ++a[c];  // 将数组a中下标为字符c的ASCII值的元素值加1
    }

    int maxx = 0, flag;  // maxx用于存储最大出现次数，flag用于存储出现次数最多的字符的ASCII值

    // 找出ASCII值在97到122（小写字母a-z）之间出现次数最多的字符
    for(int i = 97; i <= 122; ++i) {  
        if(a[i] > maxx) {  // 如果当前字符出现次数大于maxx
            maxx = a[i];  // 更新最大出现次数
            flag = i;  // 更新出现次数最多的字符的ASCII值
        }
    }

    cout << (char)flag << " " << maxx << endl;  // 输出出现次数最多的字符及其出现次数，并换行

    return 0;  
}

3. 字符的存在

【题目描述】

平安获取了一段由大写字母组成的字符，现在他想要知道哪些大写字母是没有出现的，请你帮助平安解决这个问题。

【输入格式】

输入共两行，第一行一个整数n(n<1000)，表示字符的个数。第二行包括n个字符，字符之间由空格隔开，保证都是大写英文字母。

【输出格式】

输出一行，若干个字符，字符为没有出现的大写英文字母，按照ASCII从小到大输出，中间用空格隔开。

【输入样例】

30

Z L H V L V C W Q E M T N F S Z L O B D I S K K F S Z K D D

【输出样例】

A G J P R U X Y

#include<iostream>
using namespace std;

int main() {
    int n;  // 用于存储输入的字符个数
    int a[125] = {0};  // 定义一个大小为125的整型数组a并初始化为0，用于统计字符出现的次数
    char c;  // 用于存储输入的字符

    cin >> n;  // 从标准输入读取字符的个数

    // 循环n次，输入字符并统计出现次数
    for(int i = 1; i <= n; ++i) {  
        cin >> c;  // 从标准输入读取一个字符
        ++a[c];  // 将数组a中下标为字符c的ASCII值的元素值加1
    }

    // 输出ASCII值在65到90（大写字母A-Z）之间且出现次数为0的字符
    for(int i = 65; i <= 90; ++i) {  
        if(a[i] == 0)  // 如果该大写字母未出现过
            cout << (char)i << " ";  // 输出该大写字母，并输出一个空格
    }

    return 0;  
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

c++14