直方图

题目描述

给定一个非负整数数组，统计里面每一个数的出现次数，只统计到数组里最大的数 $F_{\max}$ （ $F_{\max} < 10000$ ）。输入第一行是数组大小 $n$ （ $1 \le n \le 10000$ ），紧接着一行是数组的 $n$ 个元素。按顺序输出 $0, 1, \dots, F_{\max}$ 中每个数的出现次数，一行一个数；没有出现过的数输出 $0$ 。

样例：输入 5 和 1 1 2 3 1，最大值是 3，因此统计 $\{0,1,2,3\}$ ，输出依次为 0 3 1 1（每行一个数）。

思路

把值当下标开桶，读入时给桶 $A_i$ 加一，一遍扫描就同时得到全部频数，复杂度 $O(n + F_{\max})$ 。桶的初值就是 0，天然覆盖"没出现过输出 0"；统计到 $F_{\max}$ 为止，共输出 $F_{\max}+1$ 行。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 19:26
# update_at: 2026-09-29 19:26

import sys
from collections import Counter


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 数组大小：只用于界定输入流，计数本身不需要它
    freq = Counter(data)  # 桶排思想：每个数出现几次就往对应桶里加一

    top = max(freq)  # 只统计到数组里最大的数为止
    # 从 0 逐桶输出，没出现过的桶 Counter 里查不到，补 0
    counts = (freq.get(x, 0) for x in range(top + 1))
    print('\n'.join(map(str, counts)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 02:26
 * update_at: 2026-10-05 02:26
 */
#include <cstdio>

typedef long long ll; // 题目数据统一用 long long

const int MAXX = 10000; // Fmax < 10000，桶下标最大值

int n;
int bucket[MAXX + 5]; // bucket[x] 表示值 x 的出现次数，桶初值为 0，天然覆盖"没出现过输出 0"

int main() {
    scanf("%d", &n);
    ll fmax = 0; // 数组里的最大值，决定统计到哪个数为止
    for (int i = 1; i <= n; ++i) {
        ll x;
        scanf("%lld", &x);
        bucket[x]++;
        if (x > fmax) fmax = x; // 顺手更新最大值
    }
    // 按顺序输出 0..Fmax 每个数的出现次数，没出现的桶保持 0
    for (int i = 0; i <= fmax; ++i)
        printf("%d\n", bucket[i]);
    return 0;
}

目录

题目描述

思路

参考代码