leetcode: Number of Digit One

问题描述：

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Hint:

1. Beware of overflow.

原问题链接：https://leetcode.com/problems/number-of-digit-one/

 

问题分析

解法一：

    这个问题粗看起来有一种很简单直观的解法，就是每次计算一个数字里所包含1的个数。然后遍历所有数字把它们的个数加起来。一个简单的实现如下：

 

public static int countDigitOld(int n) {
        int count = 0;
        for(int i = 1; i <= n; i++) {
            count += count1InInteger(i);
        }
        return count;
   }

   private static int count1InInteger(int n) {
        int count = 0;
        while(n != 0) {
            count += (n % 10 == 1) ? 1: 0;
            n /= 10;
        }
        return count;
   }

    这里就是通过对一个数不停的除以10，然后求它当前最低位是否为1。然后将这些求得的值加起来。再将这个方法应用到1到n的所有数字中。这种方法的整体执行时间比较长，它的时间复杂度为O(NlogN)。所以在实际中如果数字n比较大，它的执行时间还是会比较长的。

 

方法二：

    针对上述的问题，有没有更加高效的解法呢？我们可以尝试从给定一个数字它所在的范围来考虑。对于一个数字来说，如果我们能够统计推导出它在某个位为1的数字个数，再将所有的数字的个数加起来，这样不就是我们要求的结果了么？那么这种方法是否可行呢？我们先根据一个小的示例来推导一下：

 

1位数

假设数字n是1位数的情况：

    这个时候数字n只能取0到9。那么当n >= 1的时候，出现的个数为1，当n < 1的时候，出现的个数为0。

 

2位数

再看数字n是2位数的情况：

    这个时候情况稍微复杂一点。我们针对几种情况来考虑。当n刚好为最小的2位数即10的时候，出现1的数字就两个，1和10。所以总的出现次数为2。

    n为11的时候呢，出现1的数字有1, 10, 11。对于数字11来说，它的个位和十位都出现了1，如果我们按照各位数字出现1的个数来统计，就有1和11两个数字，然后按照10位数字来统计就有10和11。虽然11统计了两次，但是它里面数字1也出现了两次，正好和我们统计的结果是一样的。这里在个数出现的数字1的数字总数是2， 在10位出现数字1的总数是2。因此总的出现次数为4。

    粗看前面这两个数字，似乎也没有什么规律可循，我们再看看数字12。它在个位上出现1的数字有1， 11。而在10位上出现1的数字则有10, 11, 12。10位上出现的数字1的个数为3。这种情况下出现1的总数字数为5。

     这个时候，我们似乎发现一点点规律。对于10位数字上出现1的个数，如果它的十位数正好是1，则它的个数为个位数上的值加1。比如12，它在十位数上出现1的个数为3个，而它的个位数是2。如果这个时候个位数是3的话，它的值可以延伸到13，则在十位数上多一个出来。

    那么对于十位数的数字大于1的情况呢？比如23。它个位数上的数字为1的数字有这些：1, 11, 21 。它十位数上数字为1的数字有: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19。总共有13个。

    针对上述的情况我们可以针对两位数有一个这样的总结，如果个位数的数字大于等于1，则个位数为1的个数为10位数的数字加1。否则就等于10位数的数字。而十位数的数字呢，如果它大于1，则个数为10，如果等于1则为个位数的数字加1。

 

3位数

    现在我们按照前面针对2位数的情况来套一下3位数的示例，看看是否适用。假设有数字100，对于它的个位数出现1的个数来说，按照前面的推断，它是取决于它的高位的数字。当个位数小于1的话，它出现的次数为10位数的数字。在这里如果引申到它的高位数的数字，是否符合条件呢？这里个位数为1的数字有1， 11, 21,31， 41， 51， 61， 71， 81， 91。正好10个数字。和我们的推断符合。如果个位数大于等于1呢？比如101或者102。出现1的数字除了上述的10个，还要101。也符合它的出现个位为高位数加1的情况。

    那么对于十位的数字呢？比如前面的100来说，它出现1的次数为10, 11, 12... 19。正好10个。如果数字小于110，那么它的数字还是取决于它的高位数，也就是10。如果数字大于等于110呢？比如110， 则10位数字的个数为11。而对于111或者112来说呢？它出现的个数还和低位的数字相关。实际上它是相当于低一位的数字2 + 1，再加上它高位的数字1 × 10。那么对于十位数字大于2的3位数情况呢？比如说123。它出现的数字情况为10， 11...19， 然后就是110, 111, ...119。正好20个。恰好为高位数的数字 (1 + 1) × 10。

    因此对于3位数来说，里面十位数包含1的个数可以这么概括，如果十位数的数字为0，则它出现的个数为高位数 × 10。比如101, 201, 301等，它们里面十位数出现1的数目分别为10， 20, 30。如果十位数的数字为1，则它出现的个数为高位数×10 + 低位数 + 1。比如110， 111，它里面十位数出现1的个数分别为11， 12 。如果十位数的数字大于1，则它出现的个数为高位数的数字 + 1再乘以10，比如120, 121，123等，它们里面十位数出现1的个数为20。这是在3位数里针对10位数总结出来的规律。那么对于百位数来说，该是个什么样的情形呢？

    比如说101， 110， 111等数字来说。因为它的百位数是1，如果按照前面的规律来套的话，它的高位数不存在，也可以说就是0，这样它的高位数 = 0，再乘以10，则为0，同时再把它的低位数个数 + 1，我们来看对不对。对于101来说，它在百位数上出现的数字是1的数字有100， 101。对于110来说，它出现这些的有100, 101,... 110，正好11个。那么对于百位数上大于1的数字来说呢？比如200， 210,221， 223等。200以内的百位为1的数字为100, 101...199，实际上有100个。也就是说，对于百位数大于1的数字来说，它应该是它的高位数加1再乘以100。所以，这里我们前面假设的乘以10是针对10位数字的，对于百位数字的应该乘以100。那么对于千位的数字呢？我们应该也可以这么来推导。

 

    我们可以总结出这么一个更加通用一点的规律，对于一个某一位的数字来说，如果它为0，则它这个位置所出现1的个数为它高位数的值乘以当前它所在的进位。比如说它是个位，则高位值乘以1，十位则高位值乘以10。比如说100，它的10位出现1的数字的个数为它高位的1乘以它当前的进位10，所以表示10。同理，求它个位数出现1的个数则为它的高位数10在乘以它当前的进位1，结果也是10。

   如果这个数字为1呢，则它这个位置所出现1的个数为它高位数的值× 当前的进位 + 低位数 + 1 。比如说110里面十位的位置，它的值为10 + 1 = 11。

    而如果这个数字大于2，则它这个位置所出现的1的个数为它高位数的值加1再乘以10，比如说220, 230等，它在十位出现1的数字的个数为30。

    这样，有了这么一大通的分析和推导，我们终于知道怎么来实现这个问题了。首先定义一个factor，来计算在某个进位上它的值，比如说个位它就是1，十位它就是10，百位它就是100...

    然后计算某个数字的高位部分highNum，它相当于n / (factor * 10)。比如当考虑个位数字的时候，需要截取的就是10位及以上的，所以需要除以当前的进位 × 10。

    对于数字的低位部分lowNum呢，它的实现如下lowNum = n - (n / factor) * factor。这样就正好把比当前进位更低位的给取出来了。

    而对于当前位的数字currNum，它的求法则是currNum = (n / factor) % 10 。

    这样，我们再根据currNum的值来判断累加每次的值就得到最终的结果了。于是我们可以得到如下的代码：

 

public class Solution {
    public int countDigitOne(int n) {
        int count = 0;
        long factor = 1;
        long lowerNum = 0;
        long higherNum = 0;
        long currNum = 0;
        while(n / factor != 0) {
            lowerNum = n - (n / factor) * factor;
            currNum = (n / factor) % 10;
            higherNum = n / (factor * 10);
            if(currNum > 1) count += (higherNum + 1) * factor;
            else if(currNum == 1) count += higherNum * factor + lowerNum + 1;
            else count += higherNum * factor;
            factor *= 10;
        }
        return count;
    }
}

     上述算法的时间复杂度为O(ln(N)/ln(10) + 1)，速度和前面的比起来确实快多了。

 

总结

   对于求给定一个非负整数所在范围内各个位置出现数字1的解法确实比较有挑战性。如果不是能够有耐心推导出后面这个规律的话，会比较艰难。而且根据这个问题还可以有一些变化，比如求里面出现其他数字的总数以及针对不同数制，比如八进制二进制的情况，这些值得深入分析举一反三。

 

参考材料

编程之美