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超出这个范围,需要进行相应的判断或者报错处理。
整体的时间复杂度是 ,其中 n 是输入数字。
文章来源:https://blog.csdn.net/m0_62110645/article/details/135330478
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!