剑指offer 面试题43. 1～n整数中1出现的次数（中）& LeetCode 233. 数字 1 的个数（难）

考查应聘者面对复杂问题的思维能力。要想找到时间复杂度为 \(O(logn)\) 的方法，应聘者需要有严密的数学思维能力，并且还要通过分析具体例子一步步找到通用的规律。这些能力在实际工作中面对复杂问题的时候都非常有用。

Question

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

示例 1： 

1
2
输入：n = 12
输出：5
示例 2： 
1
2
输入：n = 13
输出：6
限制：1 <= n < 2^31

测试用例

功能测试（输入5、10、55、99等）。 边界值测试（输入0、1等）。 性能测试（输入较大的数字，如10000、21235等）。

本题考点

考查应聘者做优化的激情和能力。最原始的方法大部分应聘者都能想到。当面试官提示还有更快的方法之后，应聘者千万不要轻易放弃尝试。虽然想出时间复杂度为 \(O(logn)\) 的方法不容易，但应聘者要展示自己追求更快算法的激情，多尝试不同的方法，必要的时候可以要求面试官给出提示，但不能轻易说自己想不出来并且放弃努力。 考查应聘者面对复杂问题的思维能力。要想找到时间复杂度为 \(O(logn)\) 的方法，应聘者需要有严密的数学思维能力，并且还要通过分析具体例子一步步找到通用的规律。这些能力在实际工作中面对复杂问题的时候都非常有用。

Intuition

基础思路

将 \(1 \sim n\) 的个位、十位、百位、...的 \(1\) 出现次数相加，即为 \(1\) 出现的总次数。

设数字 \(n\) 是个 \(x\) 位数，记 \(n\) 的第 \(i\) 位为 \(n_i\)，则可以将 \(n\) 写为 \(n_{x}, n_{x-1}, \cdots n_{2}, n_{1}\)： - 称 " \(n_i\)" 为当前位 ，记为 cur ， - 将 " \(n_{i-1} n_{i-2} \cdots n_{2} n_{1}\)" 称为低位 ，记为 low ； - 将 " \(n_{x} n_{x-1} \cdots n_{i+2} n_{i+1}\)" 称为高位 ，记为 high 。 - 将 \(10^i\) 称为位因子 ，记为 digit 。

某位中 \(1\) 出现次数的计算方法，根据当前位 cur 值的不同，分为以下三种情况：

  1. 当 cur = 0 时： 此位 \(1\) 的出现次数只由高位 high 决定，计算公式为：

\[ high \times digit \]

  1. 当 cur = 1 时： 此位 \(1\) 的出现次数由高位 high 和低位 low 决定，计算公式为：

\[ high \times digit + low + 1 \]

  1. 当 cur = 2, 3, ... , 9 时：此位 \(1\) 的出现次数只由高位 high 决定，计算公式为：

\[ (high + 1) \times digit \]

Snipaste_2020-05-12_14-13-52

上述情况的推导过程请看参考链接

变量递推公式

设计按照 “个位、十位、...” 的顺序计算，则 \(high / cur / low / digit\) 应初始化为：

1
2
3
4
high = n // 10
cur = n % 10
low = 0
digit = 1 # 个位

因此，从个位到最高位的变量递推公式为：

1
2
3
4
5
while high != 0 or cur != 0: # 当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出
   low += cur * digit # 将 cur 加入 low ，组成下轮 low
   cur = high % 10 # 下轮 cur 是本轮 high 的最低位
   high //= 10 # 将本轮 high 最低位删除，得到下轮 high
   digit *= 10 # 位因子每轮 × 10

复杂度分析

时间复杂度 \(O(\log n)\) ： 循环内的计算操作使用 \(O(1)\) 时间；循环次数为数字 \(n\) 的位数，即 \(\log_{10}{n}\) ，因此循环使用 \(O(\log n)\) 时间。 空间复杂度 \(O(1)\) ： 几个变量使用常数大小的额外空间。

Preference

作者：Krahets 链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def countDigitOne(self, n):
        # 对输入进行特判
        if n < 1:  return 0
        digit, res = 1, 0
        high, cur, low = n//10, n%10, 0
        # 当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出。
        while high != 0 or cur != 0:
            # 根据cur，分三种情况讨论。
            if cur == 0:  res += high * digit
            elif cur == 1: res += high * digit + low + 1
            else: res += (high + 1) * digit
            # 更新low、cur、high、digit
            low += cur * digit
            cur = high % 10
            high //= 10
            digit *= 10
        return res