【GESP】C++三级真题 luogu-B4262 [GESP202503 三级] 词频统计

GESP三级真题，字符串相关问题，对于三级来说有一定难度，难度★★★☆☆。

luogu-B4262 [GESP202503 三级] 词频统计

题目要求

题目描述

在文本处理中，统计单词出现的频率是一个常见的任务。现在，给定 $n$ 个单词，你需要找出其中出现次数最多的单词。在本题中，忽略单词中字母的大小写（即 Apple、apple、APPLE、aPPle 等均视为同一个单词）。

请你编写一个程序，输入 $n$ 个单词，输出其中出现次数最多的单词。

输入格式

第一行，一个整数 $n$，表示单词的个数；

接下来 $n$ 行，每行包含一个单词，单词由大小写英文字母组成。

输入保证，出现次数最多的单词只会有一个。

输出格式

输出一行，包含出现次数最多的单词（输出单词为小写形式）。

输入输出样例 #1

输入 #1

6
Apple
banana
apple
Orange
banana
apple

输出 #1

apple

说明/提示

对于所有测试点，$1\leq n\leq 100$，每个单词的长度不超过 $30$，且仅由大小写字母组成。

---

题目分析

解题思路

本题的解题思路如下：

1. 问题分析：
   • 需要统计n个单词中出现次数最多的单词
   • 单词不区分大小写，如”Apple”和”apple”视为同一个单词
   • 输出时需要将单词转换为小写形式
2. 核心逻辑：
   • 读取n个单词，每读取一个单词就进行处理
   • 将单词转换为小写形式进行统计
   • 记录每个单词出现的次数
   • 找出出现次数最多的单词并输出
3. 实现要点：
   • 使用字符串处理函数将单词转换为小写
   • 需要一个数据结构来存储单词及其出现次数
   • 可以使用数组或map等数据结构实现
   • 对于数组实现：
     • 需要两个数组，分别存储单词和对应的计数
     • 每读取一个单词需要在已有单词中查找
   • 对于map实现：
     • 直接使用单词作为key，计数作为value
     • 查找和更新都更为便捷
   • 注意题目给出的数据范围：
     • 1 ≤ n ≤ 100
     • 单词长度不超过30
     • 单词只包含大小写字母

复杂度分析：

• 数组实现：
  • 时间复杂度：$O(n^2)$，其中n为单词数量
  • 空间复杂度：$O(n)$，需要存储n个单词
• Map实现：
  • 时间复杂度：$O(n\log n)$，其中n为单词数量
  • 空间复杂度：$O(n)$，需要存储n个单词

---

方法一：利用大纲范围内得知识 数组处理

方法一示例代码

#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>

int main() {
    // 读取单词数量
    int n;
    std::cin >> n;
    // 记录最大出现次数
    int max_count = 0;
    // 存储不重复的单词数组
    std::string str_ary[n];
    // 存储每个单词出现的次数
    int count_ary[n] = {0};
    // 当前不重复单词的索引
    int cur_idx = 0;
    
    // 循环读取n个单词
    while (n--) {
        std::string str;
        std::cin >> str;
        // 将单词转换为小写
        std::transform(str.begin(), str.end(), str.begin(), ::tolower);
        // 标记当前单词是否已存在
        bool is_exist = false;
        
        // 在已有单词中查找是否存在
        for (int i = 0; i < cur_idx; i++) {
            if (str == str_ary[i]) {
                is_exist = true;
                // 已存在则计数加1
                count_ary[i]++;
                // 更新最大出现次数
                max_count = std::max(max_count, count_ary[i]);
                break;
            }
        }
        
        // 如果是新单词，则添加到数组中
        if (!is_exist) {
            str_ary[cur_idx] = str;
            count_ary[cur_idx]++;
            cur_idx++;
            // 更新最大出现次数
            max_count = std::max(max_count, count_ary[cur_idx - 1]);
        }
    }
    
    // 查找并输出出现次数最多的单词
    for (int i = 0; i < cur_idx; i++) {
        if (count_ary[i] == max_count) {
            std::cout << str_ary[i];
            break;
        }
    }
    return 0;
}

方法二：利用map数据结构

方法二示例代码

#include <iostream>
#include <map>
#include <string>
#include <cmath>
#include <algorithm>

int main() {
    // 读取单词数量
    int n;
    std::cin >> n;
    // 使用map存储单词及其出现次数
    std::map<std::string, int> count_m;
    // 记录最大出现次数
    int max_count = 0;
    // 循环读取n个单词
    while (n--) {
        std::string str;
        std::cin >> str;
        // 将单词转换为小写
        std::transform(str.begin(), str.end(), str.begin(), ::tolower);
        // 更新单词出现次数并更新最大出现次数
        count_m[str]++;
        max_count = std::max(max_count, count_m[str]);
    }
    // 遍历map查找出现次数最多的单词并输出
    for (const auto& map: count_m) {
        if (map.second == max_count) {
            std::cout << map.first;
            break;
        }
    }
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。