题解

题目解析

• 输入输出：第一行输入整数 $n$ 表示单词数量，接下来 $n$ 行每行输入一个由大小写字母组成的单词。输出出现次数最多的单词（以小写形式）。
• 数据范围：$1 \le n \le 100$，每个单词长度不超过 $30$。数据规模较小，可采用简单统计方法。
• 复杂度要求：时间复杂度 $O(n \log n)$（主要来自排序）或 $O(n)$（若使用哈希表），空间复杂度 $O(n)$。
• 算法知识点：字符串处理、排序、线性扫描、大小写转换

思路解析

1. 标准化处理：读入每个单词时，遍历字符将其全部转换为小写（tolower），确保"Apple"与"apple"被视为同一单词。
2. 排序聚合：将所有单词排序（sort），使相同单词在数组中连续相邻，便于后续批量统计。
3. 扫描计数：遍历排序后的数组，维护当前单词 $s$ 及其连续出现次数 $\textit{cnt}$。当遇到不同单词时：
   • 比较 $\textit{cnt}$ 与当前最大次数 $\textit{max\_cnt}$，若更大则更新答案 $\textit{ans}$；
   • 重置 $s$ 为新单词，$\textit{cnt}$ 置 $1$。
4. 边界处理：循环结束后需再判断一次最后一个连续段的次数，避免遗漏。
5. 输出结果：打印统计得到的最高频单词（已为小写形式）。

完整代码

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

string str[200];  // 存储单词数组，大小略大于最大n=100

int main() {
    int n;
    cin >> n;
    // 读入并统一转换为小写
    for (int i = 0; i < n; i++) {
        cin >> str[i];
        for (int j = 0; j < str[i].size(); j++) {
            str[i][j] = tolower(str[i][j]);  // 关键：忽略大小写差异
        }
    }
    // 排序使相同单词相邻，便于统计
    sort(str, str + n);
    
    string s = str[0];      // 当前正在统计的单词
    int cnt = 0;            // 当前单词出现次数
    string ans = str[0];    // 答案单词
    int max_cnt = 0;        // 最大出现次数
    
    // 线性扫描统计连续段
    for (int i = 0; i < n; i++) {
        if (str[i] == s) {
            cnt++;          // 相同单词，计数+1
        } else {
            // 遇到新单词，先结算前一段
            if (cnt > max_cnt) {
                max_cnt = cnt;
                ans = s;
            }
            // 开始统计新单词
            s = str[i];
            cnt = 1;
        }
    }
    // 关键：处理最后一段（循环内未结算）
    if (cnt > max_cnt) {
        max_cnt = cnt;
        ans = s;
    }
    cout << ans << endl;
    return 0;
}