C++编程实战：统计区间内数字出现频次的两种算法

题目要求

题目背景

Bessie 处于半梦半醒的状态。过了一会儿，她意识到她在数数，不能入睡。

题目描述

Bessie 的大脑反应灵敏，仿佛真实地看到了她数过的一个又一个数。她开始注意每一个数码（0-9）：每一个数码在计数的过程中出现过多少次？
给出两个整数 M 和 N ，求在序列 [M, M+1, M+2, ..., N-1, N] 中每一个数码出现了多少次。

输入格式

第 1 行: 两个用空格分开的整数 M 和 N。

输出格式

第 1 行: 十个用空格分开的整数，分别表示数码 0 到 9 在序列中出现的次数。

输入输出样例 #1

输入 #1

129 137

输出 #1

1 10 2 9 1 1 1 1 0 1

说明/提示

数据保证，1 ≤ M ≤ N ≤ 2×10^9，N-M ≤ 5×10^5。

题目分析

解题思路

问题本质
本题要求统计在整数区间 [M, N] 内，所有数字的每一位上（0-9）出现的总次数。

解题关键
核心在于如何高效地分解并统计每个整数的每一位数字。通常有两种思路：一种是利用字符串（String）处理方法，直观易懂；另一种是使用数学运算逐位提取，效率稍高。

实现思路

1. 字符串处理法：遍历区间内的每个数，使用 std::to_string() 将其转换为字符串，然后遍历字符串的每个字符，将字符（‘0’-‘9’）映射为数字并进行计数。这种方法逻辑清晰，是处理数字分离问题的常见技巧。
2. 数学计算法：同样遍历每个数，通过循环进行 t % 10 取最低位，然后 t /= 10 移除最低位，直到该数变为0。这种方法直接操作整数，避免了字符串转换的开销。

复杂度分析

• 时间复杂度：O((N-M+1) * L)，其中 L 是数字的平均位数。由于 N-M 最大为 5e5，且数字不超过 2e9（最多10位），完全在可行范围内。
• 空间复杂度：O(1)，仅需一个固定长度为10的数组（Array）来存储结果。

示例代码

方法一：字符串处理法

#include <iostream>
#include <string>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    int count[10] = {0}; // 初始化计数器数组，所有元素为0

    for (int i = m; i <= n; i++) {
        string numStr = to_string(i); // 将当前整数转换为字符串
        for (char digitChar : numStr) { // 遍历字符串中的每一个字符
            int digit = digitChar - '0'; // 将字符'0'-'9'转换为整数0-9
            count[digit]++; // 对应数字的计数器加1
        }
    }

    // 输出结果
    for (int i = 0; i < 10; i++) {
        cout << count[i] << " ";
    }
    return 0;
}

方法二：数学计算法

#include <iostream>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    int count[10] = {0}; // 初始化计数器数组

    for (int i = m; i <= n; i++) {
        int temp = i;
        while (temp > 0) { // 当数字不为0时，继续分解
            int digit = temp % 10; // 获取个位数
            count[digit]++; // 对应数字的计数器加1
            temp /= 10; // 去掉个位数
        }
        // 注意：此循环无法处理数字0，需要单独处理区间内包含的整数0本身。
        // 但根据题目M>=1，区间内不含整数0，因此不影响。
        // 若M可能为0，需额外判断。
    }

    // 输出结果
    for (int i = 0; i < 10; i++) {
        cout << count[i] << " ";
    }
    return 0;
}

两种方法都能正确求解，字符串法更直观，数学法则展示了基础的数位处理技巧。理解并掌握这两种基础的数据处理方式，对于系统性地提升算法能力很有帮助。本题可以在洛谷题库中搜索 P1554 进行在线评测。