求一个整数区间（从1到n）内1出现的次数

题目描述

求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

暴力解法

比较简单的解法是从1到n顺次遍历，每遍历到一个数，依次求其每一位是否为1

        //暴力法，时间复杂度是O(nlogn)
        // 遍历1~n，不断迭代检查各位是不是1
        int count = 0;
        for(int i = 1;i <= n;i++){
            int a = i;
            while(a != 0){
                if(a % 10 == 1){
                    count++;
                }
                a = a / 10;
            }
        }
        return count;

我们也可以从数学的角度进行优化，寻找规律。

从简单的开始思考

如果求从1到99中1的个数，该怎么求？

可以很自然的将1到99划分为1到9的个位数以及10到99的双位数来求解。

1到9只有一个1，而10到99其实可以通过排列组合的思想来求解。
10到99这个范围包含了所有的两位数，在这个区间内，十位和个位都可以去0-9的任意10个数。
因此，我们可以分别让10到99这个区间的任意一个数的十位置1，个位可以在0-9内随意变动，同理，个位也是如此，因此我们可以求出，在10-99这个区间内，总共有10*2=20个1.

引申至任意的n

可以随便举个例子，比如n=24563。作为一个5位数，我们可以按照上文的思路将其分为一个五位数的区间和一个四位数，该四位数可以继续往下递归。

但是在每一层该如何求解是个问题，按照上文的思路，如果可以通过排列组合的思想来求解的话，我们就可以非常灵活的根据位数求解出1的个数，但是排列组合思想的前提是每一位都能从0-9随意取值。

因此鉴于上文的思路，我们可以将1-24563拆解为1-4563和4564-24563。

为什么可以这样拆解呢？我们可以先尝试按照这个思路算一算。

4564-24563有四位数也有五位数，我们可以首先将五位数可能出现的1算出来。

从10000-19999的五位数都是1，所以五位数可能出现的1的次数为10^4=10000个。

接下来算其余的四位数，由上文可知，可以通过排列组合的方式迅速求解。但是上文用排列组合是从10-99，简单来说就是每一位数都能任意从0-9取值。我们这里可以吗？

从这里就可以看出我们这样划分的思路了，从4564-24563，刚好20000个数，可以进一步划分为4564-14563和14564-24563，每一个区间从个位都千位都能任意取0-9。

由前文排列组合的规律可以轻易得到从个位到千位的所有1的个数是2410^3=8000。由此可得从4564-24563所有1的个数为18000。

附代码（java）

public class Solution {
    private int num = 0;
    public int NumberOf1Between1AndN_Solution(int n) {
        // 寻找数学规律，递归求解
        int a = n;
        int count = 0;
        while(a != 0){
            a = a / 10;
            count++;
        }
        bit(n, count);
        return num;
    }
    private void bit(int n, int count){
        if(n == 0){
            return;
        }
        if(n < 10){
            num++;
            return;
        }
        if(n / pow(10, count - 1) >  1){
            num += pow(10, count - 1);
        }else{
            num += (n % pow(10, count - 1) + 1);
        }
        num += (n / pow(10, count - 1)) * (count - 1) * pow(10, count - 2);
        bit(n % pow(10, count - 1), count - 1);
    }
    // java的幂指数运算返回的是double型，我们可以自己定义一个返回整型的求幂方法
    private int pow(int i, int n){
        if(n == 0){
            return 1;
        }
        int a = i;
        while(n > 1){
            i *= a;
            n--;
        }
        return i;
    }
}