题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

题目的主要信息：

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

举一反三：

学习完本题的思路你可以解决如下题目：

JZ17. 打印从1到最大的n位数

JZ15. 二进制中1的个数

方法一：按位统计法（推荐使用）

思路：

数字都是由位数组成，某一位上面是1的个数是一定的，因此我们可以根据这个来处理。

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

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

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

$\lfloor n\mathrm{/}10^{i+1}\rfloor \ast 10^i+min(max(n\mathrm{\%}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)$

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

具体做法：

• step 1：准备一个基础变量，记录位数，从1开始，每轮循环扩大10倍。
• step 2：从1开始，即个位开始，直到基础变量大于n，每次按照公式统计相应位置1的个数。

图示：

Java实现代码：

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

C++实现代码：

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int res = 0;
        //MulBase = 10^i
        long long MulBase = 1;
        //每位数按照公式计算
        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;
    }
};

Python实现代码：

class Solution:
    def NumberOf1Between1AndN_Solution(self , n: int) -> int:
        res = 0
        #MulBase = 10^i
        MulBase = 1
        #每位数按照公式计算
        i = 0
        while MulBase <= n:
            i += 1
            #根据公式添加
            res += (n // (MulBase * 10)) * MulBase + min(max(n % (MulBase * 10) - MulBase + 1, 0), MulBase)
            #扩大一位数
            MulBase *= 10 
        return res

复杂度分析：

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

方法二：暴力统计法（扩展思路）

思路：

有人或许会觉得按照位数一次性统计整体想起来有点绕，我们可以试一下这种简单的暴力方法。

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

具体做法：

• step 1：从1遍历到n，查看每一个数字。
• step 2：对于每个数字，用连除法每次判断最后一位数字是否为1，并进行计数。

Java实现代码：

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

C++实现代码：

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

Python实现代码：

class Solution:
    def NumberOf1Between1AndN_Solution(self , n: int) -> int:
        res = 0
        #遍历1-n
        for i in range(1, n + 1):
            #遍历每个数的每一位
            j = i
            while j > 0:
                #遇到数字1计数
                if j % 10 == 1:
                    res += 1
                j = j // 10
        return res

复杂度分析：

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