【剑指Offer】面试题43：1~n整数中1出现的次数

发表于 | 分类于 | 阅读次数:

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

思路 1：穷举

最直接的思路就是：遍历 1~n，找出每个数字中 1 出现的次数。如何找出某个数字中 1 出现的次数呢？对 10 求余，判断数字个位数是否为一，如果结果等于 1 则数字的个位数为 1，否则数字的个位数不为 1；如果这个数字大于 10，则除以 10 之后再进行求余操作。

我们来分析这个算法的时间复杂度，n 这个数字的十进制表示的长度为 $log_{10 }n$，因此求余除法操作的时间复杂度是 O(logn)，我们需要遍历 n 次，因此整个算法的时间复杂度是 O(nlogn)。这样的时间复杂度比较高，我们需要思考更快的算法。

思路 2：排列

我们把 n 设置的大一些，让 n=21345，以便于之后的分析。为了更好的阐述这个算法，我们先来就具体的例子来分析一遍。

  1. 我们首先把分析对象分成两部分，1~21345 分成 1~19999 和 20000~21345
  2. 先对第一部分 1~19999 进行分析。计算 1 出现的次数实际上可以理解为十进制表示中某一位为 1 的排列的个数。因此，1~19999 中，当万位为 1 时其余 4 位为任意数字的排列的个数为 $10*10*10*10=10^4=10000$；当千位为 1 时，万位只能取 0 或 1，其他位取任意数字，的排列的个数为 $2*10*10*10=2000$；同理，百位为 1、十位为 1、个位为 1 的排列次数都是 $2*10*10*10=2000$。因此，1~19999 中，总的排列的个数为 $10000+2000*4=18000$
  3. 然后对第二部分 20000~21345 进行分析，因为我们将 1 出现的次数理解成十进制表示中某一位为 1 的排列的个数，所以 20000~21345 可以转换成 0~1345。于是这个部分就变成了求解 1~1345（0 去掉不影响）中 1 出现的次数
  4. 对于 1~1345 我们可以根据步骤 1 和 2 递归的求解。把 1~1345 分成 1~999 和 1000~1345。效仿于第 2 步骤的分析，1~999 中 1 出现的次数为 $10*10*10=1000$。1000~1345 可以转换成 1~345 加上 345 次
  5. 对于 1~345 我们可以根据步骤 1 和 2 递归的求解。把 1~345 分成 1~299 和 300~345。效仿于第 2 步骤的分析，1~299 中 1 出现的次数为 $10*10+2*3*10=260$。300~345 可以转换成 1~45
  6. 对于 1~45 我们可以根据步骤 1 和 2 递归的求解。把 1~45 分成 1~39 和 40~45。效仿于第 2 步骤的分析，1~39 中 1 出现的次数为 $10+4=14$。40~45 可以转换成 1~5
  7. 1~5 中 1 出现的次数为 1
  8. 因此，1~21345 中 1 出现的次数为 $18000+1000+345+260+14+1=19620$

根据以上的分析，我们将这个算法进行总结：计算 1 出现的次数实际上可以理解为十进制表示中某一位为 1 的排列的个数，因此我们可以使用递归的方法，将 n 从十进制表示的最高位到最低位一步一步计算 1 出现的次数。这个算法的递归深度是 $log\,n$，其他的操作都是常数级别的，因此总的时间复杂度为 $O(log\,n)$。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        // 特殊输入的检查
        if (n < 1)
            return 0;

        // 穷举法
        int count = 0;
        for (int i = 1; i <= n; i++) {
            count += calNumOf1(i);
        }
        return count;
    }

    private int calNumOf1(int k) {
        int count = 0;
        int a = k;
        while (true) {
            if (a == 0)
                break;
            int lastDigit = a % 10;
            if (lastDigit == 1)
                count++;
            a /= 10;
        }
        return count;
    }
}