[已解决]统计数字问题

艺术生

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

跳转到最佳答案楼层

艺术生

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

def count(index,n):                    #index: 当前正在统计的数字
    num, low, temp, copyn = 0,0,1,n    #temp:当前位数, low: 当前位数以下的数, num = 统计数字index的个数
    if(index):
        while(n):
            if(n%10 > index):          #由高位决定当前位数的index出现的次数
                num += (n//10 +1)*temp
            elif(n%10 < index):
                num += (n//10)*temp
            else:
                num += (n//10)*temp + low+1   #不仅由高位决定index出现的次数，还有低位决定
            temp *= 10
            low = copyn % temp
            n //= 10
    else:
        while(n):
            if(n%10 == 0):    #由高位和低位决定
                 num += (n//10-1)*temp + low+1
            else:             #仅由高位决定
                num += (n//10)*temp
            temp *= 10
            low = (copyn % temp) 
            n //= 10
    return num
n = int(input('请输入页码：'))
for i in range(10):
    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

def count(n):
    dict1 = {}
    f = open('D:/Desktop/test/a/b/count.txt','w+')
    for i in range(n):
        f.write(str(i))
    f.seek(0,0)
    b = f.readline()
    print(b)
    for i in range(10):
        dict1.setdefault(str(i),str(b.count(str(i))))
        print('数字%d一共出现了%d次。'%(i,b.count(str(i))))
    f.close()
    return dict1
c = count(100)
print(c)

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

jackz007

def count(m):
    d = [0] * 10
    for n in range(1 , m + 1):
        while n:
            i = n % 10
            d[i] += 1
            n //= 10
    return d

d = [str(i) for i in range(10)]
e = count(int(input()))
print(dict(zip(d , e)))

       运行实况：

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

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

D:\00.Excise\Python>