[算法] 从1到n整数中1出现的次数

从1到n整数中1出现的次数

剑指offer： 整数中1出现的次数

题目描述：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1，10，11和12，1一共出现了5次。

基本思路：从1到n遍历，得到一个数字中1出现的次数，然后累加，得到最终结果。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int result = 0;
        
        for(int i = 1; i <= n; i++){
            result += NumberOf1(i);
        }
        
        return result;
    }
    
    int NumberOf1(int n){
        int result = 0;
        
        while(n){
            if(n % 10 == 1){
                result++;
            }
            n /= 10;
        }
        
        return result;
    }
};

上面算法，数字n有O(logn)位，要循环判断n个数字，时间复杂度为O(nlogn).希望不用计算每一个数字中包含1的个数，而是寻找1出现的规律。
分析每个数位上出现1的情况，比如分析百位上为1, i = 100：

• 百位上大于1，比如 n = 21245, 高位 a = n / i = 212，低位 b = n % i = 45
  百位为1的情况为 001 ** ~ 211**共22种，其中**为00 ~ 99共100个，因此为(a / 10 + 1) * i
• 百位上等于1，比如 n = 21145, 高位 a = n / i = 211，低位 b = n % i = 45
  百位为1的情况为 001** ~ 201**共21种，其中**为00 ~ 99共100个，还有21100~21145共46个，因此为 ( a / 10 )* i + ( b + 1)
• 百位上等于0，比如 n = 21045, 高位 a = n / i = 211，低位 b = n % i = 45
  百位为1的情况为 001** ~ 201**共21种，其中**为00 ~ 99共100个，因此为 ( a / 10 )* i

数位上为0,1时，为 a / 10；数位上大于1时，为 a / 10 + 1.
可以总结为( a + 8 ) / 10 * i + ( a % 10 == 1) * ( b + 1).

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int result = 0;
        
        for(int i = 1; i <= n; i *= 10){
            int a = n / i;
            int b = n % i;
            result += (a + 8) / 10 * i + (a % 10 == 1) * (b + 1);
        }
        
        return result;
    }
};

拓展：从1到n整数中2出现的次数

程序员面试金典：2的个数

题目描述：给定一个正整数n，请返回0到n的数字中2出现了几次。

基本思路：同“从1到n整数中1出现的次数”

class Count2 {
public:
    int countNumberOf2s(int n) {
        // write code here
        int result = 0;
        
        for(int i = 1; i <= n; i *= 10){
            int a = n / i;
            int b = n % i;
            result += (a + 7) / 10 * i + (a % 10 == 2) * (b + 1);
        }
        
        return result;
    }
};