引言:
这个题在原书的配套习题解答中,描述得比较简略,我不太看得懂,于是按自己的思路做了一遍。
问题描述:
一本书有n页,页码为1,2,.. N,(注意,页码的格式,0不会在最前面)
问在这所有的页码中,0-9这10个数字,分别有多少个?
比如11页的书,
数字 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
次数 | 1 | 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
分析:
1、穷举法,for(i=1; i<=n; i++) 分解每一个页码,然后统计,可以得到结果,但时间复杂度太高,为nlogn,显然不是我们理想中的答案。
2、
以n=3267,m=4(位)为例,如果页码是从第0页开始,且格式是:0000,0001,0002,3266,3267
如果是数字1:
在第1位(千位)的次数是:1000个(1000-1999)
在第2位(百位)的次数是:,400个,(0100-0199,1100-1199,2100-2199,3100-3199)
即千位的0-3共4个,4100=400;
在第3位的次数是:,330个(0010-0019,3210-3219);即千位和百位00-32共33个,3310=330;
在第4位上的次数是:000-326共327个;
所以1的个数为:1000+400+330+327=2057个;
如果是3:
在第1位的次数是:268,是的,就是后面几位;
在第2位的次数是:(0300-0399,1300-1399,2300-2399,0),300个;
在第3位的次数是:00-32共33个,330个
在第4位的次数是:0003--3263,327个,
所以3的个数为:267+300+330+327=1224个;
如果是6:
在第1位的次数:0
在第2位的次数:0600-0699,1600-1699,2600-2699,300个
在第3位的次数是:(0060-0069)--(3160--3169) 320个, 3260-3267,8个
在第4位的次数是:0006--3266,共327个;
300+320+8+327=955个;
总结:
把数字n存放在数组中,a[4]={3,2,6,7},把数字0-9和此数组每一位依次比对。
如果小于,cnt = (n/10(m-i)+1)*10(m-i-1)
如果等于,cnt = n/10^(m-i) * 10^(m-i-1) + n%(10^(m-i-1)) + 1;
如果大于:cnt = n/(10^(m-i)) * 10^(m-i-1)
代码如下:
这个复杂度为logn,比较满意。
好久没写代码了,有点手生。