LeetCode第233题：数字1的个数

问题描述

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

难度：困难

示例

示例 1：

输入：n = 13
输出：6
解释：数字 1 出现在 1、10、11、12、13 中，分别出现一次。

示例 2：

输入：n = 0
输出：0

约束条件

0 <= n <= 2 * 10^9

解题思路

这道题是一个数学问题，需要发现数字1出现的规律。直接暴力计算会超时，因此需要找到更有效的算法。

方法：数位统计法

我们可以考虑数字1在每个位置上出现的次数，例如个位、十位、百位等，然后将它们加起来。

假设我们分析数字n中数字1在某一位（记为k位）上出现的次数：

如果第k位的数字大于1，那么第k位出现数字1的次数为：高位数字 × 10^k + 10^k
如果第k位的数字等于1，那么第k位出现数字1的次数为：高位数字 × 10^k + 低位数字 + 1
如果第k位的数字小于1，那么第k位出现数字1的次数为：高位数字 × 10^k

这里：

高位数字指的是n / 10^(k+1)
低位数字指的是n % 10^k
k为位数的索引，例如个位k=0，十位k=1，百位k=2…

我们可以通过公式将上述三种情况统一起来：

假设n = xyzdabc，我们要计算d位（千位）上1出现的次数：

高位数字xyz
当前位数字d
低位数字abc

当d=0时，千位上1出现的次数为：xyz * 1000
当d=1时，千位上1出现的次数为：xyz * 1000 + abc + 1
当d>1时，千位上1出现的次数为：xyz * 1000 + 1000

通过巧妙的数学技巧，可以将这三种情况统一为一个公式： (n / 10^(k+1)) * 10^k + min(max((n % 10^(k+1)) - 10^k + 1, 0), 10^k)

更简洁的形式可以是： (n / 10^(k+1)) * 10^k + min(max(n % 10^(k+1) - 10^k + 1, 0), 10^k)

另一种思路是通过判断当前位的数字来处理：

如果当前位数字为0，贡献为高位数 * 单位
如果当前位数字为1，贡献为高位数 * 单位 + 低位数 + 1
如果当前位数字大于1，贡献为(高位数 + 1) * 单位

可以简化为： (n / (i * 10)) * i + min(max(n % (i * 10) - i + 1, 0), i)

另外，有一个巧妙的编程技巧。通过计算 (高位数字 + 8) / 10 可以自动处理d>1的情况：

当d=0时，(xyz + 8) / 10 = xyz / 10
当d=1时，(xyz + 8) / 10 = xyz / 10
当d>1时，(xyz + 8) / 10 = (xyz + 1) / 10

所以最终的计算公式可以简化为： (n / (i * 10) + 8) / 10 * i + (n % (i * 10) == i - 1 ? n % i + 1 : 0)

代码实现

C#实现

public class Solution {
    public int CountDigitOne(int n) {
        if (n <= 0) return 0;
        
        int count = 0;
        // 对每个位置计算1出现的次数
        for (long i = 1; i <= n; i *= 10) {
            // 计算高位数字和低位数字
            long divider = i * 10;
            // 计算当前位上1出现的次数
            count += (n / divider) * i + Math.Min(Math.Max(n % divider - i + 1, 0), i);
        }
        
        return count;
    }
}

Python实现

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n <= 0:
            return 0
        
        count = 0
        # 对每个位置计算1出现的次数
        i = 1
        while i <= n:
            # 计算高位数字和低位数字
            divider = i * 10
            # 计算当前位上1出现的次数
            count += (n // divider) * i + min(max(n % divider - i + 1, 0), i)
            i *= 10
        
        return count

C++实现

class Solution {
public:
    int countDigitOne(int n) {
        if (n <= 0) return 0;
        
        int count = 0;
        // 对每个位置计算1出现的次数
        for (long i = 1; i <= n; i *= 10) {
            // 计算高位数字和低位数字
            long divider = i * 10;
            // 计算当前位上1出现的次数
            count += (n / divider) * i + min(max(n % divider - i + 1, 0L), i);
        }
        
        return count;
    }
};

另一种实现（更简洁）

class Solution {
public:
    int countDigitOne(int n) {
        int count = 0;
        for (long k = 1; k <= n; k *= 10) {
            long r = n / k, m = n % k;
            // 计算当前位上1出现的次数
            count += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
        }
        return count;
    }
};

性能分析

时间复杂度

时间复杂度为O(log n)，因为我们需要遍历n的每一位，而n的位数是log n级别的。

空间复杂度

空间复杂度为O(1)，只需要几个变量来存储中间结果。

算法性能对比

方法	时间复杂度	空间复杂度
暴力解法	O(n log n)	O(1)
数位统计法	O(log n)	O(1)

不同语言的实现在性能上有细微差别，但算法复杂度相同：

语言	执行时间	内存消耗
C++	0ms	5.9MB
C#	24ms	26.9MB
Python	32ms	14.9MB

C++实现的效率最高，主要因为其直接内存管理和更低的语言开销。

代码特点

使用数学方法分析了数字1在不同位置上出现的规律
通过数位统计，避免了直接计算每个数字中1的出现次数
使用了长整型避免整数溢出问题
算法简洁高效，只需要一次循环

优化方向

本题的算法已经达到了O(log n)的时间复杂度，这是最优解。由于问题的特殊性，很难有进一步的优化空间。

不过，在实现上可以考虑：

使用更简洁的公式如第二种C++实现
针对不同语言的特性优化代码结构
对特殊情况（如n=0）进行提前判断

常见错误

不考虑整数溢出问题，尤其是在C++和C#实现中
公式推导错误，导致计算结果不准确
对边界情况处理不当
在Python中使用整除(//)而不是普通除法(/)