论坛 › 数据结构与算法 › 统计数字问题

艺术生 发表于 2021-3-12 20:13:02

统计数字问题

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

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

艺术生 发表于 2021-3-13 21:16:40

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

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 发表于 2021-3-12 20:13:03

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

liuzhengyuan 发表于 2021-3-12 20:36:50

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

艺术生 发表于 2021-3-12 20:41:15

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


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

yuedong 发表于 2021-3-13 10:17:20

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

yuedong 发表于 2021-3-13 10:50:05

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 发表于 2021-3-13 12:02:44

本帖最后由 jackz007 于 2021-3-13 12:07 编辑

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

d =
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>

查看完整版本: 统计数字问题