计算区间内数字出现次数的算法及Python实现

本文章提供了一种高效算法，用于计算给定区间内特定数字出现的次数。例如，在1到11之间，数字1出现了4次。

问题描述:

给定一个区间[1, n]和一个数字x (0 ≤ x ≤ 9)，计算数字x在该区间内所有整数中出现的次数。

算法描述:

读取输入: 读取区间上限n和目标数字x。2. 初始化计数器: 创建一个计数器count，初始值为0。3. 遍历区间: 使用循环遍历区间[1, n]内的每个整数。4. 统计数字出现次数: 在每次循环中： - 将当前整数转换为字符串。 - 使用字符串的count方法统计目标数字x在字符串中出现的次数。 - 将统计结果累加到计数器count中。5. 输出结果: 循环结束后，输出计数器count的值，即为数字x在区间[1, n]内出现的总次数。

**Python代码示例:**pythonn, x = map(int, input('请输入区间上限n和目标数字x，以空格分隔: ').split())count = 0

for i in range(1, n+1): count += str(i).count(str(x))

print(f'数字 {x} 在区间 [1, {n}] 内出现了 {count} 次')

代码说明:

n, x = map(int, input().split()) 读取输入的区间上限n和目标数字x。- count = 0 初始化计数器。- for i in range(1, n+1): 循环遍历区间[1, n]内的每个整数。- count += str(i).count(str(x)) 将当前整数转换为字符串，并统计目标数字出现的次数，累加到计数器中。- print(f'数字 {x} 在区间 [1, {n}] 内出现了 {count} 次') 输出最终结果。

算法复杂度:

该算法的时间复杂度为O(nlogn)，其中n为输入的区间上限。

示例:

输入: 11 1

输出: 数字 1 在区间 [1, 11] 内出现了 4 次

总结:

本文介绍了一种简单高效的算法，利用字符串处理方法统计区间内数字出现的次数，并提供了Python代码实现。该算法易于理解和实现，可以有效解决该类问题。