计数 题解

题目分析

题目要求统计从 1 到 n 的所有整数中，数字 k 出现了多少次。例如 n=25，k=2 时，数字 2 在哪些数中出现：2、12、20、21、22、23、24、25，其中 22 出现了两次 2，因此总次数为 9 次。

数据范围中，1 ≤ n ≤ 1000，1 ≤ k ≤ 9，n 的值很小，可以直接采用暴力枚举的做法。

解题思路

我们可以依次检查 1 到 n 中的每一个整数，统计该整数的各个十进制位中有多少个数字等于 k，然后把所有统计结果累加起来。

关键在于如何统计一个整数中数字 k 的出现次数：

• 不断取该数的个位（对 10 取模），如果等于 k 则计数加一。
• 然后将该数整除 10，去掉个位。
• 重复上述过程直到该数变为 0。

这样就能得到单个数字中 k 的出现次数。

算法说明

1. 定义一个函数 check(x, k)，用来返回整数 x 中数字 k 出现的次数：
   • 初始化计数器 cnt = 0
   • 当 x > 0 时执行循环：
     • 取个位 tmp = x % 10
     • 若 tmp == k 则 cnt++
     • 去掉个位 x = x / 10
   • 返回 cnt
2. 在主函数中：
   • 读入 n 和 k
   • 初始化答案 ans = 0
   • 用循环 i 从 1 到 n：
     • ans += check(i, k)
   • 输出 ans

时间复杂度分析

对于每个整数 i，check 函数需要循环它的位数次，对于 n 最大为 1000，每个数最多有 4 位（如 1000）。因此总操作次数约为 n × 4，最多约 4000 次，完全可以在一秒内完成，时间复杂度为 O(n log₁₀ n)。

参考代码

cpp
复制
1#include <iostream>
2using namespace std;
3
4// 统计整数 x 中数字 y 出现的次数
5int check(int x, int y) {
6    int cnt = 0;
7    while (x > 0) {
8        int tmp = x % 10;   // 取出个位
9        if (tmp == y) {     // 如果等于目标数字
10            cnt++;          // 计数器加一
11        }
12        x = x / 10;         // 去掉个位
13    }
14    return cnt;
15}
16
17int main() {
18    int n, k;
19    cin >> n >> k;
20    int ans = 0;
21    for (int i = 1; i <= n; i++) {
22        ans += check(i, k); // 累加每个数中 k 的出现次数
23    }
24    cout << ans << endl;
25    return 0;
26}

代码解释

• check 函数：通过反复取个位并除以 10 的方式逐位检查，统计等于 k 的位数。
• 主函数中循环变量 i 从 1 到 n，依次将每个数传入 check 并将结果累加到 ans。
• 最后输出累加结果，即为 k 在 1 到 n 中出现的总次数。