Java第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)，避免双重循环反复比较。

完整程序

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 计数数组（桶）：下标对应数字值，元素对应出现频次
        int[] cnt = new int[101];

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            if (x >= 0 && x <= 100) {
                cnt[x]++;
            }
        }

        // 顺序扫描桶数组，非零频次的数字天然按升序输出
        for (int v = 0; v <= 100; v++) {
            if (cnt[v] > 0) {
                System.out.println(v + ":" + cnt[v]);
            }
        }
    }
}

运行示例

输入：

6
1 2 1 2 2 3

输出：

1:2
2:3
3:1