计算从1到n所有整数中包含数字1个数

《计算从1到n所有整数中包含数字1个数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算从1到N的所有整数中包含数字1的个数今天看到一道有趣的算法题，题目如下：N为正整数，计算从1到N的所有整数中包含数字1的个数。比如，N=10，从1，2...10，包含有2个数字1。 相信很多人都能立刻得出以下的解法： for(n:N) {         判断n包含1的个数；         累加计数器； }这是最直接的解法，但遗憾的是，时间复杂程度为O(N*logN)。因为还需要循环判断当前的n的各位数，该判断的时间复杂程度为O(logN)。接下来就应该思考效率更高的解法了。说实话，这道题让我想起另外一道简单的算法题：N为正整数，计算从1到N的整数和。很多人

2、都采用了循环求解。然后利用初等数学知识就知道S=N*(N+1)/2，所以用O(1)的时间就可以处理。再回到本道题目，同理应该去寻找到结果R与N之间的映射关系。分析如下：假设N表示为a[n]a[n-1]...a[1]，其中a[i](1<=i<=n)表示N的各位数上的数字。c[i]表示从整数1到整数a[i]...a[1]中包含数字1的个数。x[i]表示从整数1到10^i-1中包含数字1的个数，例如，x[1]表示从1到9的个数，结果为1；x[2]表示从1到99的个数，结果为20；当a[1]=0时，c[1]=0;当a[1]=1时，c[1]=1;当a[1]>1时，c[1]=

3、1; 当a[2]=1时，c[2]=a[1]+1+c[1]+x[1];当a[2]>1时，c[2]=a[2]*x[1]+c[1]+10; 当a[3]=1时，c[3]=a[2]*a[1]+1+c[2]+x[2];当a[3]>1时，c[3]=a[3]*x[2]+c[2]+10^2;...... 以此类推当a[i]=1时，c[i]=a[i-1]*...*a[1]+1+c[i-1]+x[i-1];当a[i]>1时，c[i]=a[i]x[i-1]+c[i-1]+10^(i-1);  实现的代码如下：Java代码 1.public static int search(int _n

4、)     2.{     3.    int N = _n/10;     4.    int a1 = _n%10,a2;     5.    int x = 1;  6.    int ten = 10;  7.    int c = a1 == 0?0:1;  8.    while(N > 0)     9.    {     10.        a2 = N%10;  11.        if(a2 == 0);  1.        else if(a2 == 1)c = a1 + 1 + x + c;     2.        else c 

5、= a2*x + c + ten;     3.        a1 = 10*a1 + a2;       4.        N /=10;     5.        x = 10*x + ten;  6.        ten *= 10;   7.    }     8.    return c;     9.}  publicstaticintsearch(int_n){intN=_n/10;inta1=_n%10,a2;intx=1;intten=10;intc=a1==0?0:1;while(N>0){a2=N%10;if(a2==0);elsei

6、f(a2==1)c=a1+1+x+c;elsec=a2*x+c+ten;a1=10*a1+a2;N/=10;x=10*x+ten;ten*=10;}returnc;}  而以上解法的时间复杂程度只有O(logN)今天看到一道有趣的算法题，题目如下：N为正整数，计算从1到N的所有整数中包含数字1的个数。比如，N=10，从1，2...10，包含有2个数字1。 相信很多人都能立刻得出以下的解法： for(n:N) {         判断n包含1的个数；         累加计数器； }这是最直接的解法，但遗憾的是，时间复杂程度为O(N*logN)。因为还需要循环判断当

7、前的n的各位数，该判断的时间复杂程度为O(logN)。接下来就应该思考效率更高的解法了。说实话，这道题让我想起另外一道简单的算法题：N为正整数，计算从1到N的整数和。很多人都采用了循环求解。然后利用初等数学知识就知道S=N*(N+1)/2，所以用O(1)的时间就可以处理。再回到本道题目，同理应该去寻找到结果R与N之间的映射关系。分析如下：假设N表示为a[n]a[n-1]...a[1]，其中a[i](1<=i<=n)表示N的各位数上的数字。c[i]表示从整数1到整数a[i]...a[1]中包含数字1的个数。x[i]表示从整数1到10^i-1中包含数字1的个数，例如，

8、x[1]表