题目链接

记数问题

题目描述

试计算在区间 [1, n] 的所有整数中，数字 x (0 ≤ x ≤ 9) 一共出现了多少次。

输入描述:

  • 在一行中输入两个整数 n 和 x，用空格隔开。

输出描述:

  • 输出一个整数，表示数字 x 在区间 [1, n] 中出现的总次数。

示例说明:

  • 输入 11 1：在 1, 2, ..., 10, 11 中，数字 1 出现在 1, 10, 11。其中 11 包含两个 1，所以总次数是 1 + 1 + 2 = 4。

解题思路

本题要求统计一个数字在某个整数区间内所有数中出现的总次数。对于给定的数据范围，最直观的暴力解法是可行的，其思路如下：

  1. 遍历区间: 使用一个 for 循环，遍历从 1 到 n 的每一个整数 i。

  2. 检查每个数: 对于循环中的每一个数 i，我们需要计算数字 x 在 i 中出现了多少次。这个子问题有两种常见的解决方法：

    • 方法A：数学方法 (模除法) 这是最基础、最通用的方法。我们可以用一个 while 循环来逐位分解数字 i：

      • digit = i % 10：取出 i 的个位数。
      • 判断 digit 是否等于 x，如果等于，则计数器加一。
      • i = i / 10：去掉 i 的个位数，为下一次循环做准备。
      • 循环直到 i 变为 0。

    • 方法B：字符串转换法 在很多高级语言中，这是一个更简洁的方法。

      • 将数字 i 转换成字符串。
      • 遍历字符串中的每一个字符，判断是否与 x 的字符形式相等。
      • Python 等语言甚至提供了内置的 count() 方法，可以一步到位。

  3. 累加总数: 将在每个数字 i 中统计到的出现次数，累加到一个全局的总计数器 total_count 上。

  4. 输出结果: 当外层循环（从 1 到 n）结束后，total_count 就是最终的答案。

算法步骤概览：

  • 初始化 total_count = 0。
  • for i from 1 to n:
    • current_count = count_digit_x_in(i)
    • total_count += current_count
  • 输出 total_count。

代码

#include <iostream>

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    
    int total_count = 0;
    
    // 外层循环：遍历 [1, n] 中的每个数
    for (int i = 1; i <= n; ++i) {
        int temp = i;
        // 内层循环：分解当前数 temp，检查每一位
        while (temp > 0) {
            if (temp % 10 == x) {
                total_count++;
            }
            temp /= 10;
        }
    }
    
    cout << total_count << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        
        int totalCount = 0;
        
        // 遍历 [1, n]
        for (int i = 1; i <= n; i++) {
            int temp = i;
            // 分解数字 i
            while (temp > 0) {
                if (temp % 10 == x) {
                    totalCount++;
                }
                temp /= 10;
            }
        }
        
        System.out.println(totalCount);
    }
}

n, x = map(int, input().split())

total_count = 0
# 将要查找的数字也转为字符串，方便后续比较
x_str = str(x)

# 遍历 [1, n]
for i in range(1, n + 1):
    # 将当前数字转为字符串，并使用内建的count方法
    total_count += str(i).count(x_str)
    
print(total_count)

算法及复杂度

  • 算法：暴力枚举。
  • 时间复杂度：。外层循环执行 N 次。内层循环（或字符串转换和计数）的复杂度与数字 i 的位数成正比，即 。
  • 空间复杂度：。我们只使用了常数级别的额外空间。（若考虑字符串转换，空间复杂度为 ，用于临时存储字符串，对于本题可忽略不计）。