1～n整数中1出现的次数

679 字

3 分钟

1～n整数中1出现的次数

2022-02-22

2026-10-12

数据结构与算法

「剑指Offer」Swift

一、题目#

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

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12

输出：5

示例 2：

输入：n = 13

输出：6

限制：

1 <= n < 2^31

注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、分析#

2.1 暴力#

当然遍历全部数字，进行累加理论上是可行的。但是如果真写出这样的代码就别想通过面试了🤷‍♂️。

2.2 按位分析#

我们需要知道一个前提，1出现的次数和就是1在每一位上出现的次数的和。那么我们如何计算出每一位上出现1的次数呢？

下面我们以310562为例进行一下分析。

百位#

我们想知道在这位出现1的次数，我们定义当前位的数字为 num = 5 ，其左边的所有数字为 pre = 310 ，右边的数字为 aft = 62 ，当前位为 base = 100 。

左组合数量：
- 0 ～ 310
- pre + 1
右组合数量：
- 0 ～ 99
- base
  - 因为 1 < 5 ，百位为1时位数足够，可以取到 99
  - 其实就等于当前的位，即100

次数 = (pre + 1) * base

千位#

pre = 31, num = 0, base = 1000, aft = 562

当前位为0，当为1时必须需要前面退位，如上图变化
- 前范围变为 0 ～ 30
左组合数量
- 0 ～ 30
- pre
右组合数量：
- 0 ～ 999
- base

次数 = (pre * base)

万位#

pre = 3, num = 1, base = 10000, aft = 0562

当 pre 取 0 ～ 2 时：
- 左组合数量
  - 0 ～ 2
  - pre
- 右组合数量：
  - 0 ～ 999
  - base
当 pre 取 3 时：
- 左组合数量
  - 3
  - 1
- 右组合数量：
  - 0 ～ 562
  - (aft + 1)

次数 = (pre * base) * (aft + 1)

左数 & 右数#

上面将所有三种特殊情况的次数计算方式都推导出来了。剩下推出 pre aft num 的公式即可。

根据规律推导出：
- pre = n / base / 10
- aft = n % base
- num = n / base % 10

下面我们就可以根据上面的公式完成遍历的逻辑了。

三、编码#

1
func countDigitOne(_ n: Int) -> Int {
2
    var base = 1
3
    var sum = 0
4

5
    while base <= n {
6
        let pre = n / base / 10
7
        let aft = n % base
8
        let num = n / base % 10
9

10
        if num == 1 {
11
            sum += ((pre * base) + (aft + 1))
12
        }
13
        else if num == 0 {
14
            sum += (pre * base)
15
        }
16
        else {
17
            sum += ((pre + 1) * base)
18
        }
19

20
        base *= 10
21
    }
22

23
    return sum
24
}