GESP 题解库 / 3 级题解 / [GESP202503 三级] 词频统计 · 第 8 / 28 题
GESP202503 三级 · B4262 · 简单

词频统计

给定 n 个单词,忽略大小写找出出现次数最多的那个,并以小写形式输出。

📊
n ≤ 100
数据规模
🔤
长度 ≤ 30
单词长度
⚡
O(n × L)
时间复杂度
🎯
映射计数
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 n 个单词,找出其中出现次数最多的单词。忽略字母大小写(Apple、apple、APPLE、aPPle 视为同一个单词),输出该单词的小写形式。输入保证出现次数最多的单词只会有一个。

💡
人话翻译:先把所有单词统一转成小写,然后统计每个单词出现几次,最后挑出次数最多的那个输出。关键是"先归一化,再统计",顺序不能反。

🔍 关键词提取

大小写归一化计数映射找最大值map 或排序

已知条件

项目说明
输入第一行 n;随后 n 行每行一个单词
输出出现次数最多的单词(小写)
数据范围1 ≤ n ≤ 100
单词长度不超过 30,仅含大小写字母
重要保证出现次数最多的单词唯一(不会并列)

需要解决的问题

02
思维导图
整理解题思路的全貌
📝 先归一化,再计数
📥 读入
读 n
逐个读入单词
每个都转小写
保持原序无所谓
🔤 归一化
大写字母 +32 变小写
或用 tolower()
统一后再统计
输出自然就是小写
📊 计数
map<string,int> 累加
或排序后数连续段
两者都 O(n log n) 以内
n 只有 100
🏆 找冠军
遍历所有键
记录最大次数
题目保证不并列
输出对应的键
03
样例手算推导
样例 6 个单词的统计过程

🧮 样例:Apple / banana / apple / Orange / banana / apple

先全部转成小写,再逐个计数。

1
统一转小写

Apple → apple

banana → banana

apple → apple

Orange → orange

banana → banana

apple → apple

得到 apple、banana、apple、orange、banana、apple

2
逐个计数

apple:第 1、3、6 个 → 3 次

banana:第 2、5 个 → 2 次

orange:第 4 个 → 1 次

apple 出现 3 次,是最多的

3
输出

答案是 apple(已经是小写形式)

✅ 输出 apple

📊 词频表

单词出现次数是否最多
apple3✅ 是
banana2否
orange1否
🔑
如果先统计再转小写会怎样?那样 Apple、apple、APPLE 会被当成 3 个不同的单词,每个都只出现 1 次,答案就错了。归一化必须在统计之前。
04
解法对比
map 计数 vs 排序计数

⚔️ 解法对比

🟢 map 计数(推荐) 推荐

用 map<string,int> 边读边累加,最后遍历找最大

  • 时间 O(n × L × log n)
  • 不需要保存全部单词
  • 代码短、逻辑直白
  • 还能顺便输出"出现次数"
💡
为什么推荐:读入的同时就完成计数,最后只需一趟遍历判断最大值,是词频统计的标准解法。

🟠 排序后数连续段

把单词数组排序,相同单词会相邻,数最长连续段

  • 时间 O(n log n × L)
  • 需要 O(n) 空间存所有单词
  • 要额外处理"当前段长度"
  • 代码更长
⚠️
注意:排序法必须先把所有单词都转成小写再排序,否则 Apple 和 apple 不会相邻,连续段就数错了。

📈 性能对比

方案空间代码量
map 计数O(不同单词数)约 15 行
排序计数O(n)约 25 行
05
算法流程图
读入 → 归一化 → 计数 → 找最大
开始读入 n读入一个单词 s,全部转成小写cnt[s] 加 1n 个单词都读完了吗?遍历 cnt,找出次数最大的键 best输出 best结束还有单词没读 → 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📝 词频统计器

每行输入一个单词(可多行),程序会忽略大小写统计词频并找出最多的那个。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    map<string, int> cnt;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (char &c : s) c = tolower(c);   // 归一化:统一小写
        cnt[s]++;
    }

    string best;
    int bestCnt = -1;
    for (auto &p : cnt) {                   // p.first 是单词,p.second 是次数
        if (p.second > bestCnt) {
            bestCnt = p.second;
            best = p.first;
        }
    }

    printf("%s\n", best.c_str());
    return 0;
}
🔑
为什么用 map 而不是 unordered_map?两者都能用,本题 n ≤ 100 完全没差别。map 的键有序,输出更稳定;unordered_map 平均更快但键无序。

📖 关键几行怎么看

代码作用为什么这样写
for (char &c : s) c = tolower(c);逐个字符转小写用引用才能改到原字符串,否则只是改副本
cnt[s]++计数map 的 [] 会在键不存在时自动插入 0
p.second > bestCnt找最大值严格大于即可,题目保证不并列
best = p.first记录答案存的是已经归一化过的小写单词
⚠️
三个坑:① 忘了归一化,导致同一个词被拆成多个;② 用 tolower 时没加 &,改了副本无效;③ 初始 bestCnt 设为 0,在次数可能为 0 的场景下会出错(本题每个词至少出现 1 次,设 -1 最稳)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
1
Hello
hello只有一个词,注意输出小写
3
a
a
b
a最基础计数
4
Apple
apple
APPLE
banana
apple大小写混合必须视为同一个词
6
Apple
banana
apple
Orange
banana
apple
apple题面样例
5
Zz
zZ
ZZ
zz
aa
zz4 种写法都归一化为 zz
✅
自查清单:① 归一化在统计之前吗?② 用了引用改字符吗?③ 输出的确实是次数最多的那个词?

🚨 易错点清单

⚠️
先统计后归一化:顺序反了,Apple 和 apple 会被算成两个词。
⚠️
tolower 没加引用:for (char c : s) 改的是副本,必须写 for (char &c : s)。
⚠️
输出时又转了一次小写:其实统计时已经全部是小写了,直接输出即可,再转一次也没错但多余。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n × L × log n)
空间复杂度
O(n × L)
n 最大
100
单词长度
≤ 30

时间怎么算的?

空间都用在哪?

最坏情况下 n 个单词互不相同,map 里存 n 个键值对,空间 O(n × L)。

✅ n 只有 100,任何合理写法都是瞬间完成;这题考的是归一化意识,不是效率。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 字符大小写转换
char toLower(char c) { return (c >= 'A' && c <= 'Z') ? char(c + 32) : c; }
char toUpper(char c) { return (c >= 'a' && c <= 'z') ? char(c - 32) : c; }

// 字符串整体转小写(注意引用)
for (char &c : s) c = toLower(c);

// 计数三兄弟
map<string, int> cnt;        // 有序,便于稳定输出
unordered_map<string, int> h; // 更快,但键无序
int bucket[300];             // 若键恰好是小整数,可以直接开数组

// 遍历 map 找最大值
string best; int bc = -1;
for (auto &p : cnt) if (p.second > bc) { bc = p.second; best = p.first; }

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
大小写归一化统一转小写后再统计字符串比较、去重、字典序处理
map 计数用键值对记录出现次数词频统计、去重、判断是否出现过
遍历找极值一趟扫描记录最大值的键求众数、最值、Top-1 问题
🌟
思考题:如果题目改成"输出出现次数最多的前 3 个单词,按次数从多到少、次数相同按字典序",该怎么改?(提示:把 map 里的键值对倒进 vector,写个自定义比较函数再排序。)