题目的主要信息：

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

方法一：暴力统计法

具体做法：

我们可以尝试遍历1到n的每个数字，然后对每个数字单独遍历它的每一位，检查是否是1，如果是1则计数。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int res = 0;
        for(int i = 1; i <= n; i++){ //遍历1-n
            for(int j = i; j > 0; j = j / 10){ //遍历每个数的每一位
                if(j % 10 == 1) //遇到数字1计数
                    res++;
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O\left(nlo{g}_{10}n\right)O(nlog\_\{10\}n)$O(nlog10​n)，外循环一共循环$nn$n次，内循环最大循环次数不会超过最大数字$nn$n的位数即$lo{g}_{10}nlog\_\{10\}n$log10​n
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间使用

方法二：按位统计法

具体做法：

对于每个数字统计1出现的次数太复杂了，我们可以考虑每次直接计算1到n的数字中某位上面的1出现了多少次。

假设我们要计算百位上总共有多少1：首先100-199有100个1，而1100-1199又出现了100个1，于是我们知道了每过1000个数字就会出现100个百位上的1，于是我们就有$\lfloor n/1000\rfloor \ast 100\backslash lfloor\; n/1000\; \backslash rfloor\; *\; 100$⌊n/1000⌋∗100，细分讨论一下就是：

• 当n%1000<100，百位上不会出现1；
• 当100<=n%1000<200，百位上出现的1有$n\%1000-100+1n\; \backslash \%\; 1000\; -\; 100\; +\; 1$n%1000−100+1次
• 当$n\%1000>=200n\; \backslash \%\; 1000\; >=\; 200$n%1000>=200，百位上的1一共100次

于是我们就可以得到计算公式每一位的计算公式：

$\lfloor n/10^{i+1}\rfloor \ast 10^i+min\left(max\right(n\%10^{i+1}-10^i+1,0),10^k)\backslash lfloor\; n\; /\; 10^\{i+1\}\; \backslash rfloor\; *\; 10^i\; +\; min(max(n\; \backslash \%\; 10^\{i+1\}\; -\; 10^i\; +\; 1,\; 0),\; 10^k)$⌊n/10i+1⌋∗10i+min(max(n%10i+1−10i+1,0),10k)

公式中$10^{i}10^i$10i就表示某一位，而前半部分是表示完整在循环中的，后半部分表示部分出现需要讨论的。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int res = 0;
        long long MulBase = 1;//MulBase = 10^i
        for(int i = 0; MulBase <= n; i++){ //每位数按照公式计算
            res += (n / (MulBase * 10)) * MulBase + min(max(n % (MulBase * 10) - MulBase + 1, (long long)0), MulBase);
            MulBase *= 10; //扩大一位数
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O\left(lo{g}_{10}n\right)O(log\_\{10\}n)$O(log10​n)，循环次数等于数字$nn$n的位数，位数与$nn$n呈10的对数关系
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间使用