剑指Offer对答如流系列 - 从1到n整数中1出现的次数

面试题43：从1到n整数中1出现的次数

一、题目描述

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。

二、问题分析

最容易想到的思路是通过对10求余数判断整数的个位数字是不是1。代码书写也很简单，但是如果输入的整数n比较大的时候，会有大量的运算。

1是由于数字递增出现的，而十进制影响这种出现的周期性。这本身肯定存在规律，重要的是耐心寻找，不要妄想一次性就找出来，下面的规律要比《剑指Offer》书上提到的更好点。

我们以12043来进行分析。我们从个位开始，一直到最高位，统计每一位上的1出现的次数。

我们将数字拆分成三部分，高位high，当前位cur和低位low

1. 当当前位为个位的时候，high是1204、cur是3、low不存在，设置为0。个位数为1的情况有00001 - 12041,一共是1204+1种情况。
2. 当当前位为十位的时候，high是120、cur是4、low是3，十位数字为1的情况：先考虑低位有 00010 - 00019（10种）、再综合考虑：0001X-1201X，一共是（120+1）* 10种情况。
3. 当当前位为百位的时候，high是12、cur是0、low是43，百为数字为1的情况：先考虑低位有00100 - 00199（100种），再综合考虑：000XXX-110XXX，一共是（11+1）*100种情况，注意因为不存在121XXX，最高为111XXX
4. 当当前位为千位的时候，high为1、cur是2、low是043，千位数字为1的情况：先考虑低位有01000 - 01999（1000种），在综合考虑：01XXXX - 11XXXX，一共是（1+1）*1000种情况
5. 当当前位为万位的时候，high是0、cur是1、low是2043，万位数字为1的情况：先考虑低位有10000-12043，一共是2043+1种情况。

当cur为0和1的时候需要特殊处理，其他值的时候常规处理。

再举一个数字21034

1. 当前位的数字等于0时，例如n=21034，在百位上的数字cur=0，百位上是1的情况有：00100-00199，01100-01199，……，20100~20199。一共有21*100种情况，即high*100;
2. 当前位的数字等于1时，例如n=21034，在千位上的数字cur=1，千位上是1的情况有：01000-01999，11000-11999，21000-21034。一共有2*1000+（34+1）种情况，即high*1000+(low+1)。
3. 当前位的数字大于1时，例如n=21034，在十位上的数字cur=3，十位上是1的情况有：00010-00019，……，21010-21019。一共有（210+1）*10种情况，即(high+1)*10。

对于整数n，其位数一共有lgn个，所以时间复杂度为O(logn)。

三、问题解答

    public int NumberOf1Between1AndN(int n) {
        int count=0;
        // i代表位数
        for(int i=1;i<=n;i*=10){
            //高位数字
            int high=n/(i*10);
            //低位数字
            int low= n%i;
            //当前位数字
            int cur=(n/i)%10;

            if(cur==0) {
                count+=high*i;
            } else if (cur==1){
                count+=high*i+(low+1);
            } else {
                count+=(high+1)*i;
            }
        }
        return count;
    }