Python算法例32 统计数字

2024-01-02 04:01:34

1. 问题描述

计算数字k在0~n中出现的次数,k可能是0~9中的一个数字。

2. 问题示例

n=12,k=1,在[0,1,2,3,4,5,6,7,8,9,10,11,12]中,1出现了5次(1,10,11,12)。

3. 代码实现

使用数学方法实现

数学方法:

  • 首先观察k在各个位上出现的规律。以k=1为例,我们会发现:
    • 个位上,每隔10个数,1就会出现一次;
    • 十位上,每隔100个数,1就会出现10次;
    • 百位上,每隔1000个数,1就会出现100次;
    • 以此类推。
  • 所以,我们可以通过对n进行循环遍历,依次计算每个位上1出现的次数,并累加起来即可。
  • 时间复杂度为O(logn),因为需要对n进行取整操作。
def count_digit_one(n, k):
    count = 0
    factor = 1  # 位因子,用于表示当前处理的是个位、十位、百位...
    while n // factor != 0:
        curr_digit = (n // factor) % 10  # 当前位的数字
        high_digit = n // (factor * 10)  # 更高位的数字

        if curr_digit < k:
            count += high_digit * factor
        elif curr_digit == k:
            count += high_digit * factor + (n % factor) + 1
        else:
            count += (high_digit + 1) * factor

        factor *= 10

    return count
print(count_digit_one(12,1))

这段代码中,我们通过循环遍历每个位上的数字,根据当前位的数字与k的大小关系,计算出当前位上k出现的次数,并累加到count中。最终返回count即可。

需要注意的是,以上代码假设了k在0~9之间,如果k超出这个范围,需要进行相应的判断或者报错处理。

整体的时间复杂度是 O(\log n),其中 n 是输入数字。

文章来源:https://blog.csdn.net/m0_62110645/article/details/135330478
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。