【GESP】C++三级练习 luogu-B2096 直方图

GESP C++三级练习，一维数组练习，难度★★☆☆☆。

luogu-B2096 直方图

题目要求

题目描述

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

假设 $Fmax（Fmax \le 100000）$是数组里最大的数，那么我们只统计 ${0,1,2 \ldots Fmax }$ 里每个数出现的次数。

输入格式

第一行 $n$ 是数组的大小。$1 \le n \le 100000$。

紧接着一行是数组的 $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记录每个数字出现次数
   • 输出时遍历0到max_num范围内的所有数字的出现次数
3. 实现思路：
   • 使用一个足够大的数组count_ary（大小为100005）
   • 遍历输入数组：
     • 更新最大值max_num
     • 对应位置count_ary[num]计数加1
   • 按顺序输出count_ary[0]到count_ary[max_num]
4. 复杂度分析：
   • 时间复杂度：$O(n + max_num)$
     • 遍历输入数组：$O(n)$
     • 输出统计结果：$O(max_num)$
   • 空间复杂度：$O(max_num)$，需要一个大小为max_num的计数数组

---

示例代码

#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;
}

利用array写法，纯熟悉语法

#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;
}

---

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

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

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

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