词频统计 题解

题目分析

本题要求在一组单词中找出出现次数最多的单词。输入保证出现次数最多的单词只有一个，且需要忽略大小写差异，最终输出小写形式的单词。

数据范围很小（n ≤ 100，单词长度 ≤ 30），可以直接使用字符串处理和统计的方法解决。

解题思路

1. 读入数据：首先读入整数 n，表示单词个数。
2. 统一大小写：由于忽略大小写，每读入一个单词，就将其全部转换为小写字母。这样 “Apple”“apple”“APPLE” 都会变成 “apple”。
3. 统计频率：使用一个映射（如 map 或 unordered_map），将小写单词作为键，出现次数作为值。每处理一个单词，对应的计数值加 1。
4. 记录最大次数：在更新计数的同时，维护当前出现次数的最大值 mx。
5. 输出结果：再次遍历映射，找到次数等于 mx 的单词并输出。因为题目保证答案唯一，直接输出第一个符合条件的单词即可。

整个过程逻辑简单，适合初学者练习 map 的用法和字符串处理。

算法说明

参考代码使用了 C++ 的标准模板库，具体实现如下：

• ios::sync_with_stdio(false); 和 cin.tie(nullptr); 用于关闭 C 和 C++ 输入输出流的同步，提高读取速度。
• 使用 map<string, int> cnt 来存储单词及其出现次数。map 内部会按照键的字典序自动排序，但本题中没有排序需求，使用 unordered_map 也能通过。
• 循环 n 次，每次读入一个字符串 s：
  • transform(s.begin(), s.end(), s.begin(), ::tolower); 将字符串中所有字母转为小写。::tolower 是 C 库中的函数。
  • if (!cnt.count(s)) cnt[s] = 0; 这一行其实不是必须的，因为 map 在访问不存在的键时会自动创建并初始化为 0。这里只是为了习惯性地检查，实际直接写 cnt[s]++ 即可。
  • mx = max(mx, ++cnt[s]); 更新最大出现次数。
• 最后用范围 for 循环 for (auto& pair : cnt) 遍历映射。pair.first 是单词，pair.second 是次数。若次数等于 mx，就输出该单词并结束程序（题目保证只有一个答案，但代码中加了计数器 mx_num 用于调试性检查）。

注意：输出时 pair.first 已经是小写形式，符合题目要求。

时间复杂度分析

• 读入 n 个单词，每个单词长度为 L（L ≤ 30）。字符串转小写的时间复杂度为 O(L)。
• 向 map 中插入或更新元素，每次操作的时间复杂度为 O(log M * L)，其中 M 是不同单词的数量（M ≤ n ≤ 100）。因此总时间复杂度为 O(n * L * log n)。
• 最后的遍历同样为 O(M * L)。

对于 n=100，这个复杂度完全可以在 1 秒的时间限制内运行完成，即使使用简单的算法也毫无压力。

代码实现

以下是参考代码（已添加注释）：

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5    ios::sync_with_stdio(false); // 优化输入输出速度
6    cin.tie(nullptr);
7
8    int n;
9    cin >> n;
10
11    map<string, int> cnt;   // 单词 -> 出现次数
12    int mx = -1;            // 最大出现次数
13
14    for (int i = 0; i < n; i++) {
15        string s;
16        cin >> s;
17
18        // 转换为小写
19        transform(s.begin(), s.end(), s.begin(), ::tolower);
20
21        // 计数增加，并更新最大值
22        cnt[s]++;
23        mx = max(mx, cnt[s]);
24    }
25
26    // 找出次数等于 mx 的单词并输出
27    for (auto& p : cnt) {
28        if (p.second == mx) {
29            cout << p.first << '\n';
30            break;  // 答案唯一，找到即可退出
31        }
32    }
33
34    return 0;
35}

总结

本题主要考察字符串的基本处理和计数器的使用。利用 map 或 unordered_map 可以方便地完成频率统计，而 transform 函数则简化了大小写转换的操作。对于入门练习而言，是一道非常友好的题目。