首先,我们需要分析页码中数字出现的规律,如下所示:
数字: 0 1 2 3 4 5 6 7 8 9
页码: 0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
……
可以看出,对于任意一个数字k,当它在个位数时,它会出现1次;当它在十位数时,它会出现10次;当它在百位数时,它会出现100次……
因此,我们可以枚举每一位,计算出数字k在这一位出现的次数,然后累加起来即可。
下面是一个使用 Python 的解法:
def count_digits(n: int) ->List[int]:
res = [0] * 10
for i in range(1, 11):
div = 10 ** (i - 1)
res[i - 1] = n // div * (div // 10)
res[i - 1] += min(max(n % div - div // 10 + 1, 0), div // 10)
return res
n = int(input())
print(*count_digits(n))
这个解法的时间复杂度是O(log n),空间复杂度是O(1),因此很高效。
#include "stdio.h"int main(){
int n
int a[10] = {0}
int i
scanf("%d", &n)
for (i = 1i <= ni++)
{
int k=i//这要用一个中间变量,不然的话每次while完后i=0for里i++=1;死循环了
while(k)
{
a[k%10]++
k = k/10
}
}
for (i = 0i <10i++)
printf("%d\n", a[i])
return 0
}
代码如下:#include "stdio.h"
int main(int argc, char const *argv[])
{
int n=3,m=2
int i,s=0,t
for(i=1i<=10*ni++)
{
t=i
while(t>0)
{
if((t%10)==m)
{
s++
}
t=t/10
}
if(s>=n)
{
printf("这本书一共有%d页\n",i)
break
}
}
return 0
}