[已解决]统计数字问题

艺术生

一本书的页码从自然数 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则是秒解。

跳转到最佳答案楼层

艺术生

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

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))

复制代码

amyano

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

liuzhengyuan

循环遍历每一个页码（这个应该会）
使用 a % 10 的方法来获取 a 的个位
接下来 a /= 10，（a 为 整形）
一直取位知道 a 为0

艺术生

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

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

yuedong

我有个想法，你先range(n)生成一个列表
然后将列表中的元素，全部写入到一个文件，
写入的时候以空白为结束取代\n
再从文件中读取为一个字符串
用str.count方法就可以了

yuedong

1. 
   
2. def count(n):
   
3.     dict1 = {}
   
4.     f = open('D:/Desktop/test/a/b/count.txt','w+')
   
5.     for i in range(n):
   
6.         f.write(str(i))
   
7.     f.seek(0,0)
   
8.     b = f.readline()
   
9.     print(b)
   
10.     for i in range(10):
    
11.         dict1.setdefault(str(i),str(b.count(str(i))))
    
12.         print('数字%d一共出现了%d次。'%(i,b.count(str(i))))
    
13.     f.close()
    
14.     return dict1
    
15. c = count(100)
    
16. print(c)
    

复制代码

最后除过输出还将它存为了一个字典

jackz007

1. def count(m):
   
2.     d = [0] * 10
   
3.     for n in range(1 , m + 1):
   
4.         while n:
   
5.             i = n % 10
   
6.             d[i] += 1
   
7.             n //= 10
   
8.     return d
   
9. 
   
10. d = [str(i) for i in range(10)]
    
11. e = count(int(input()))
    
12. print(dict(zip(d , e)))

复制代码

       运行实况：

1. D:\00.Excise\Python>python page.py
   
2. 101
   
3. {'0': 12, '1': 23, '2': 20, '3': 20, '4': 20, '5': 20, '6': 20, '7': 20, '8': 20, '9': 20}
   
4. 
   
5. D:\00.Excise\Python>python page.py
   
6. 80999
   
7. {'0': 32189, '1': 42300, '2': 42300, '3': 42300, '4': 42300, '5': 42300, '6': 42300, '7': 42300, '8': 33300, '9': 32300}
   
8. 
   
9. D:\00.Excise\Python>

复制代码