[已解决]统计数字问题

艺术生

一本书的页码从自然数 1 开始顺序编码直到自然数 n。书的页码按照通常的习惯编排，
每个页码都不含多余的前导数字 0。例如，第 6 页用数字 6 表示，而不是 06 或 006 等。数
字计数问题要求对给定书的总页码 n，计算出书的全部页码中分别用到多少次数字 0，1， 2，…，9。       

        大佬们，可以给我个思路吗？实在想不出什么好的算法 。。

最佳答案

月排行榜 / 总排行榜

amyano

2021-3-12 20:13:03

凭借记忆帮楼主找到了时间复杂度为O(log n)的解法， 可参考剑指offer第43题，为一个扩展。 0作为特殊情况考虑
暴力法很容易理解， 但是时间复杂度O(n log n)， 当n取整形最大值的时候 暴力法需要几十分钟， logn则是秒解。

跳转到最佳答案楼层

艺术生

liuzhengyuan 发表于 2021-3-12 20:36
循环遍历每一个页码（这个应该会）
使用 a % 10 的方法来获取 a 的个位
接下来 a /= 10，（a 为 整形）

遍历还是会的，就是想用一些算法来解决这道题，让计算机秒出答案

艺术生

解铃还须系铃人，我去群里问了一位大佬，终于解出了来了，大家敬请享用
        此题对于初学算法的小伙伴含金量挺高哦，在此也谢谢尽力想帮助我的鱼油们，（虽然答案并不是那么，，，，）

1. def count(index,n):                    #index: 当前正在统计的数字
   
2.     num, low, temp, copyn = 0,0,1,n    #temp:当前位数, low: 当前位数以下的数, num = 统计数字index的个数
   
3.     if(index):
   
4.         while(n):
   
5.             if(n%10 > index):          #由高位决定当前位数的index出现的次数
   
6.                 num += (n//10 +1)*temp
   
7.             elif(n%10 < index):
   
8.                 num += (n//10)*temp
   
9.             else:
   
10.                 num += (n//10)*temp + low+1   #不仅由高位决定index出现的次数，还有低位决定
    
11.             temp *= 10
    
12.             low = copyn % temp
    
13.             n //= 10
    
14.     else:
    
15.         while(n):
    
16.             if(n%10 == 0):    #由高位和低位决定
    
17.                  num += (n//10-1)*temp + low+1
    
18.             else:             #仅由高位决定
    
19.                 num += (n//10)*temp
    
20.             temp *= 10
    
21.             low = (copyn % temp)
    
22.             n //= 10
    
23.     return num
    
24. n = int(input('请输入页码：'))
    
25. for i in range(10):
    
26.     print(count(i,n))

复制代码