C 语言第36题：统计数组中各元素出现次数（数值范围较小时）

题目

从标准输入读入 n 个位于 [0, 99] 范围内的整数，统计各个数值出现的频次并输出（仅输出出现次数大于 0 的数值）。

输入格式：第一行输入整数个数 n；第二行输入 n 个非负整数。

输出格式：按数值升序输出每行一个统计结果，格式为 数值: 出现次数。

数据范围与约定：1 ≤ n ≤ 1000，数组元素 0 ≤ a[i] < 100。

思路与算法

1. 计数数组（哈希桶原理）
当数据取值范围有限且非负时，可以直接开辟固定大小的频次统计数组 int cnt[100] = {0};。将元素值作为数组下标，读入 v 时直接 cnt[v]++。

2. 空间与时间
以空间换时间，统计耗时 O(n)，查表输出耗时 O(100)，避免双重循环反复比较。

完整程序

#include <stdio.h>

int main(void)
{
    // 计数数组（桶）：下标对应数字值，元素对应出现频次，初始化为 0
    int n, x, cnt[101] = {0};
    if (scanf("%d", &n) != 1 || n < 1) {
        return 1;
    }

    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        if (x >= 0 && x <= 100) {
            cnt[x]++;
        }
    }

    // 顺序扫描桶数组，非零频次的数字天然按升序输出
    for (int v = 0; v <= 100; v++) {
        if (cnt[v]) {
            printf("%d:%d\n", v, cnt[v]);
        }
    }
    return 0;
}

运行示例

输入：

6
1 2 1 2 2 3

输出：

1:2
2:3
3:1