43.从1到n整数中1出现的次数（中等）

考点：本题考查时间效率

题目描述

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

思路一：

对每个数字都要做除法和求余运算，以求出该数字中1出现的次数

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
       int count=0;
       for(int i=n;i>0;i--){
           for(int j=i;j>0;j/=10){
               if(j%10==1) count++;
             }
        }
    return count;
    }
}

这种思路是最容易想到的思路。如果输入数字n，n有O(logn)位，需要判断每一位是不是1，时间复杂度是O(nlogn)。当n非常大的时候，需要大量的计算，运算效率不高。

思路二：每次去掉最高位进行递归***

把从1到21345的所有数字分为两段，一段是从1-1345，另一段是从1346-21345。
先看1346-21345中1出现的次数。
1的出现分为两种情况：首先分析1出现在最高位万位的情况，在1346-21345中，1出现在10000-19999这10000个数字的最高位万位中，一共出现了10000次，即10^4。
接下来分析1出现在除最高位之外的其他四位数中的情况。1346-21345这20000个数字中后4位中1出现的次数，分成两段，1346-11345和11346-21345，每一段剩下的4位数字中，选择其中一位是1，其余三位可以在0-9这10个数字中任意选择，根据排列组合原则，总共出现次数2410^3=8000次。
1-1345中1的出现的次数，可以根据递归求解。这是要把1-21345分成1-1345和1346-21345两段的原因。因为21345的最高位去掉就变成了1345，便于采用递归的思路。

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        String str = String.valueOf(n);//将整数n转换为字符串str
        int first = str.charAt(0) - '0';
        int length = str.length();
 
        if(length == 1 && first == 0)
            return 0;
        if(length == 1 && first > 0)
            return 1;
        //假设s是"21345"
        //numFirstDigit是数字10000-19999的第一位中1的数目
        int numFirstDigit = 0;
        if(first > 1){
            numFirstDigit = powerBase10(length - 1);
        }
        else if(first == 1){
            numFirstDigit = Integer.valueOf(str) - powerBase10(length - 1) + 1;
        }
         //numOtherDigit是1346-21345除第一位之外的数位中1的数目
        int numOtherDigit = first * (length - 1) * powerBase10(length - 2);
        //numRecursive是1-1345中1的数目
        int numRecursive = NumberOf1Between1AndN_Solution(Integer.valueOf(str) - first * powerBase10(length - 1));
        return numFirstDigit + numOtherDigit + numRecursive;
    }
    public static int powerBase10(int n){
        int result = 1;
        for(int i = 0;i < n;i++){
            result *= 10;
        }
        return result;
    }
}