0233-数字 1 的个数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 10:44:20 2023-09-13 10:44:20 Updated    

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

**输入：** n = 13
**输出：** 6

示例 2：

**输入：** n = 0
**输出：** 0

提示：

  • 0 <= n <= 109

方法一：枚举每一数位上 $1$ 的个数

思路

根据题目要求，我们需要统计 $[0, n]$ 范围内所有整数中，数字 $1$ 出现的个数。由于 $n$ 的范围最大为 $10^9$，它是一个 $10$ 位整数，因此我们可以考虑枚举每一个数位，分别统计该数位上数字 $1$ 出现的次数，最后将所有数位统计出的次数进行累加即可得到答案。

为了直观地叙述我们的算法，下面我们以「百位」进行举例，对于几个不同的 $n$ 手动计算出答案，随后扩展到任意数位。

以 $n = 1234567$ 为例，我们需要统计「百位」上数字 $1$ 出现的次数。我们知道，对于从 $0$ 开始每 $1000$ 个数，「百位」上的数字 $1$ 都会出现 $100$ 次，即数的最后三位每 $1000$ 个数都呈现 $[000, 999]$ 的循环，其中的 $[100, 199]$ 在「百位」上的数字为 $1$，共有 $100$ 个。

$n$ 拥有 $1234$ 个这样的循环，每个循环「百位」上都出现了 $100$ 次 $1$，这样就一共出现了 $1234 \times 100$ 次 $1$。如果使用公式表示，那么这部分出现的 $1$ 的次数为：

$$
\lfloor \frac{n}{1000} \rfloor \times 100
$$

其中 $x$ 表示将 $x$ 向下取整，那么 $\lfloor \dfrac{n}{1000} \rfloor$ 就表示 $n$ 拥有的完整的 $[000, 999]$ 循环的数量。

对于剩余不在完整的循环中的部分，最后三位为 $[000, 567]$，其中 $567$ 可以用 $n \bmod 1000$ 表示，其中 $\bmod$ 表示取模运算。记 $n’ = n \bmod 1000$，这一部分在「百位」上出现 $1$ 的次数可以通过分类讨论得出：

  • 当 $n’ < 100$ 时，「百位」上不会出现 $1$；

  • 当 $100 \leq n’ < 200$ 时，「百位」上出现 $1$ 的范围为 $[100, n’]$，所以出现了 $n’ - 100 + 1$ 次 $1$；

  • 当 $n’ \geq 200$ 时，「百位」上出现了全部 $100$ 次 $1$。

可以发现，当 $n’ < 100$ 时，$n’ - 100 + 1$ 的值小于等于 $0$，而我们希望得到 $0$ 的答案；$n’ \geq 200$ 时，$n’ - 100 + 1$ 的值大于 $100$，而我们希望得到 $100$ 的答案，因此我们可以总结归纳出这一部分在「百位」上 $1$ 的出现次数为：

$$
\min\big(\max(n’ - 100 + 1, 0), 100\big)
$$

此时，我们就得到了 $[0, n]$ 中「百位」上数字 $1$ 出现的次数为：

$$
\lfloor \frac{n}{1000} \rfloor \times 100 + \min\big(\max(n \bmod 1000 - 100 + 1, 0), 100\big)
$$

我们用类似的方法可以计算出在其它数位上数字 $1$ 出现的次数。如果该数位可以表示为 $10^k$（例如 $k=0, 1, 2$ 分别表示「个位」「十位」「百位」），那么数字 $1$ 出现的次数为：

$$
\lfloor \frac{n}{10^{k+1}} \rfloor \times 10^k + \min\big(\max(n \bmod 10^{k+1} - 10^k + 1, 0), 10^k\big) \tag{1}
$$

用形象化的语言描述 $(1)$ 式的意义即为：

当数位为 $10^k$ 时，最后的 $k$ 个数位每 $10^{k+1}$ 个数会循环一次，并且其中包含 $10^k$ 个 $1$，由于 $n$ 包含 $\lfloor \dfrac{n}{10^{k+1}} \rfloor$ 个完整的循环，那么这一部分的 $1$ 的个数为 $\lfloor \dfrac{n}{10^{k+1}} \rfloor \times 10^k$。不在循环中的部分还有 $n \bmod 10^{k+1}$ 个数，这一部分的 $1$ 的个数为 $n \bmod 10^{k+1} - 10^k + 1$，如果这个值小于 $0$，那么调整为出现 $0$ 次；如果这个值大于 $10^k$，那么调整为出现 $10^k$ 次。

算法

我们可以从小到大枚举 $k$。如果 $n \geq 10^k$，说明 $n$ 包含 $10^k$ 对应的数位，我们通过 $(1)$ 式计算这一数位 $1$ 的个数并累加，否则退出枚举。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countDigitOne(int n) {
        // mulk 表示 10^k
        // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        // 但为了让代码看起来更加直观，这里保留了 k
        long long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0LL), mulk);
            mulk *= 10;
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int countDigitOne(int n) {
        // mulk 表示 10^k
        // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        // 但为了让代码看起来更加直观，这里保留了 k
        long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
            mulk *= 10;
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int CountDigitOne(int n) {
        // mulk 表示 10^k
        // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        // 但为了让代码看起来更加直观，这里保留了 k
        long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (int) (n / (mulk * 10) * mulk) + (int) Math.Min(Math.Max(n % (mulk * 10) - mulk + 1, 0), mulk);
            mulk *= 10;
        }
        return ans;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def countDigitOne(self, n: int) -> int:
        # mulk 表示 10^k
        # 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        # 但为了让代码看起来更加直观，这里保留了 k
        k, mulk = 0, 1
        ans = 0
        while n >= mulk:
            ans += (n // (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0), mulk)
            k += 1
            mulk *= 10
        return ans
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
var countDigitOne = function(n) {
    // mulk 表示 10^k
    // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
    // 但为了让代码看起来更加直观，这里保留了 k
    let mulk = 1;
    let ans = 0;
    for (let k = 0; n >= mulk; ++k) {
        ans += (Math.floor(n / (mulk * 10))) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
        mulk *= 10;
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func countDigitOne(n int) (ans int) {
    // mulk 表示 10^k
    // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
    // 但为了让代码看起来更加直观，这里保留了 k
    for k, mulk := 0, 1; n >= mulk; k++ {
        ans += (n/(mulk*10))*mulk + min(max(n%(mulk*10)-mulk+1, 0), mulk)
        mulk *= 10
    }
    return
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
int countDigitOne(int n) {
    // mulk 表示 10^k
    // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
    // 但为了让代码看起来更加直观，这里保留了 k
    long long mulk = 1;
    int ans = 0;
    for (int k = 0; n >= mulk; ++k) {
        ans += (n / (mulk * 10)) * mulk + fmin(fmax(n % (mulk * 10) - mulk + 1, 0LL), mulk);
        mulk *= 10;
    }
    return ans;
}

复杂度分析

  • 时间复杂度：$O(\log n)$。$n$ 包含的数位个数与 $n$ 呈对数关系。

  • 空间复杂度：$O(1)$。

 Comments
On this page
0233-数字 1 的个数