中级 · 计数数组

数字出现次数

统计一个数里每个数字出现的次数，按数字升序输出。你的第一个计数数组 —— 直方图和投票统计背后的同一套模式。

一句话答案用一个 10 格的数组统计每个数字出现次数，然后只把出现过的数字按 digit:count 升序打印 —— 用固定桶数组代替排序。

题目

输入: 一个非负整数（0 <= n <= 1000000000）。

输出: 每个出现过的数字一行：数字:次数，按升序。

样例:

输入输出
1223331:1
2:2
3:3

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 用数组当计数器

int count[10] = {0};，每次切下一位就 count[n % 10]++;。

提示 2 — 只打印出现过的

遍历 0–9，只在 count[d] > 0 时输出 —— 输出零次数会被判错。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int count[10] = {0};
    while (n > 0) {
        count[n % 10]++;
        n /= 10;
    }
    for (int d = 0; d <= 9; d++) {
        if (count[d] > 0) cout << d << ":" << count[d] << endl;
    }
    return 0;
}

这就是计数排序和直方图的模式：用值当下标，用自增来计数。和两桶版本对照看。

深度解析

为什么这样做对

用值当下标的计数数组，是最简单的哈希表：不用算哈希、不会冲突、天生 O(1) 查找。

代价

O(n + 10) 时间、O(10) 空间。那个常数 10 就是它比排序快一个量级的原因。

常见错法

  • 拿 char 当下标拿到的是 ASCII 码（'9' 是 57），不是 9。要减 '0'。
  • 把十个桶全打印出来，而不是只打印出现过的，会被精确比对判错。

下一步

同样的数组，换个聚合方式：矩阵求和。

记住这两句

  • 值当下标 = 不用哈希的哈希表。
  • '9' - '0' == 9，这个偏移量就是全部技巧。
🐞 这段是错的 —— 点开,亲手让它挂一次

把十个桶全打印了，而不是只打印出现过的

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int count[10] = {0};
    while (n > 0) {
        count[n % 10]++;
        n /= 10;
    }
    for (int d = 0; d <= 9; d++) {
        cout << d << ":" << count[d] << endl;
    }
    return 0;
}