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

题目

统计数组中各元素出现次数（数值范围较小时）

思路

读数组后，cnt[v] 对合法下标 v 自增；再遍历值域输出 v: cnt[v]，或只输出出现过的值。

解题分析

值域 0～100 时用计数数组 cnt[v] 比排序再扫更简单，O(n) 时间。值域很大时改用 map 或排序后线性扫重复段。

完整程序

#include <stdio.h>

int main(void)
{
    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