计算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的整数和。

很多人都采用了循环求解。然后利用初等数学知识就知道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] = 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);

 

 

实现的代码如下：

    public static int search(int _n)   
    {   
        int N = _n/10;   
        int a1 = _n%10,a2;   
        int x = 1;
        int ten = 10;
        int c = a1 == 0?0:1;
        while(N > 0)   
        {   
            a2 = N%10;
            if(a2 == 0);
            else if(a2 == 1)c = a1 + 1 + x + c;   
            else c = a2*x + c + ten;   
            a1 = 10*a1 + a2;     
            N /=10;   
            x = 10*x + ten;
            ten *= 10; 
        }   
        return c;   
    }

 

 

而以上解法的时间复杂程度只有O(logN)

 

如果您路过这里，您有更好的解法吗？：）

评论

6 楼 waiting90 2009-01-11  

lggege 写道

StringBuffer.append() 将它们拼成一个String, 再从头到尾数

这样很慢，很慢...

5 楼 pandonix 2008-06-19  

非常感谢ywergs，以前的算法确实存在问题。惭愧啊，分析不仔细。
问题原因：
代码中没有考虑到a1=0的情况，因为如果a1=0，则c1=0。造成当a2=1，a1=0时，按照c2=a1+1+x1+c1来计算，而c1被初始化为1,所以c2=0+1+1+1=3。
问题解决：
初始化c1时，需要根据a1来初始化，其中c1=a1==0?0:1
这样一来就可以测试：
N(20) = 2*1+10 = 12;N(19) = 9 + 1 + 1 + 1 = 12;所以N(20) = N(19)
N(10) = 0 + 1 + 1 = 2;

再次感谢ywergs，欢迎继续讨论和拍砖

4 楼 ywergs 2008-06-19  

恕我愚笨，我怎么觉得LZ的这个有点问题呢？
比如，当我们用20来测试时，他应该走入else语句！
那么 c20 = 2 * 1 + 1 + 10 = 13
但从直观角度来看数字20 和 19 他们区间包含一个数应该是一样的，可是，如果算19的话，应该走的是if的，这时候， c19 = 9 + 1 + 1 + 1 = 12
从而有：
    c20 != c19
当然，我也为LZ的精湛思路所折服！
不过我也没有想到一个比较好的方法！
写到这里，发觉根本不用20来做测试，就是用10来做测试就有问题了！
按照LZ的思路，10的时候，算出来 应该是 3 ，可是，1-10之间只有2个1的！

3 楼 jasongreen 2008-06-18  

google面试题阿

2 楼 pandonix 2008-06-18  

楼上的解法不错，但时间复杂程度也是O(N+logN)以上，同时也忽略了API,Integer.parseInt的处理时间。

1 楼 lggege 2008-06-18  

StringBuffer.append()

将它们拼成一个String, 再从头到尾数