C++直方图统计实战：数组应用与GESP三级真题解析

题目要求

题目描述

给定一个非负整数数组，统计里面每一个数的出现次数。我们只统计到数组里最大的数。

假设 m 是数组里最大的数，那么我们只统计 {0,1,2,...,m} 里每个数出现的次数。

输入格式

第一行是数组的大小 n。

紧接着一行是数组的 n 个元素。

输出格式

按顺序输出每个数的出现次数，一行一个数。如果没有出现过，则输出 0。

对于例子中的数组，最大的数是 3，因此我们只统计 {0,1,2,3} 的出现频数。

输入输出样例 #1

输入 #1

5
1 1 2 3 1

输出 #1

0
3
1
1

题目分析

解题思路

本题的核心是掌握数组作为计数器的基本应用，这是编程中处理频率统计问题的经典方法。

解题思路如下：

1. 问题本质：统计数组中每个数字出现的次数，但只需统计从 0 到数组最大值这个范围内的数字。
2. 解题关键：
   • 遍历数组，找出其中的最大值 max_num。
   • 使用一个独立的计数数组 count_ary 来记录每个数字出现的次数。
3. 实现步骤：
   • 初始化一个足够大的数组 count_ary（例如大小为 100005，根据题目数据范围设定），所有元素置零。
   • 遍历输入数组的每个数字 num：
     • 更新当前最大值 max_num。
     • 将计数数组对应位置 count_ary[num] 的值加 1。
   • 最后，循环输出 count_ary[0] 到 count_ary[max_num] 的值。
4. 复杂度分析：
   • 时间复杂度：O(n + max_num)，需要遍历输入数组和输出范围。
   • 空间复杂度：O(max_num)，需要一个大小为数据最大值的计数数组。

示例代码

版本一：使用C风格数组

这是最直接和基础的实现方式，适合理解数组计数原理。

#include <cmath>
#include <iostream>
// 定义一个大小为100005的整型数组，用于统计每个数字出现的次数
// 数组大小取100005是因为题目限制了输入数字的最大值不超过100000
// 初始化所有元素为0
int count_ary[100005] = {};
int main() {
    // 读取数组大小
    int n;
    std::cin >> n;
    // 记录数组中的最大值，初始化为-1
    int max_num = -1;
    // 遍历输入的n个数字
    for (int i = 0; i < n; i++) {
        // 读取当前数字
        int cur_num;
        std::cin >> cur_num;
        // 更新最大值
        max_num = std::max(max_num, cur_num);
        // 统计当前数字出现的次数
        count_ary[cur_num]++;
    }
    // 输出从0到最大值之间每个数字出现的次数
    for (int i = 0; i <= max_num; i++) {
        std::cout << count_ary[i] << "\n";
    }
    return 0;
}

版本二：使用 std::array (熟悉现代C++语法)

此版本使用 std::array 替代C风格数组，提供了更好的类型安全和边界检查功能（通过 at() 方法），是更现代的C++实践。

#include <array>
#include <cmath>
#include <iostream>
// 定义一个大小为100005的数组，用于统计每个数字出现的次数
// 使用std::array代替C风格数组，提供边界检查功能
std::array<int, 100005> count_ary = {};
int main() {
    // 读取数组大小n
    int n;
    std::cin >> n;
    // 记录输入数字中的最大值，初始化为-1
    int max_num = -1;
    // 遍历输入的n个数字
    for (int i = 0; i < n; i++) {
        // 读取当前数字
        int cur_num;
        std::cin >> cur_num;
        // 更新最大值
        max_num = std::max(max_num, cur_num);
        // 使用at()函数统计当前数字出现次数，提供边界检查
        count_ary.at(cur_num)++;
    }
    // 输出从0到最大值之间每个数字出现的次数
    for (int i = 0; i <= max_num; i++) {
        std::cout << count_ary.at(i) << "\n";
    }
    return 0;
}

本题“luogu-B2096 直方图”可在洛谷题库进行在线评测。通过解决这类问题，可以夯实数组的基础操作，并理解其在算法与数据结构中作为基础数据结构的重要性。