数字1的个数

🎯 问题描述（来源于LeetCode）

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

💻 代码实现

初始思路

class Solution:
    def countDigitOne(self, n: int) -> int:
        a=0
        b=0
        for i in range(1,n+1):
            num=str(i).count("1")
            b = num+a
            a = b
        return b

但由于时间复杂度$O(Nlog(N))$在$10^9$附近时过大，所以进行优化。优化思路在改进对当前数字进行1的计数。由字符串统计变为按位统计：

具体方法

设当前考察的位为第 k 位（从个位开始，k=0,1,2…），该位的权值 base = 10^k。对于整数 n，定义：

• high = n // (base * 10) （高位数字）

• cur = (n // base) % 10 （当前位数字）

• low = n % base （低位数字）

根据当前位 cur 的值，该位出现 1 的次数为：

1. cur == 0：high * base

2. cur == 1：high * base + low + 1

3. cur >= 2：(high + 1) * base

数学解释：

• 当 cur == 0 时，该位为 1 的情况仅由高位决定（高位从 0 到 high-1），每种高位对应的低位有 base 种情况（0 到 base-1）。

• 当 cur == 1 时，除了上述情况外，还包括高位为 high 时，低位从 0 到 low 的 low+1 种情况。

• 当 cur >= 2 时，高位可以从 0 到 high，每种高位对应的低位有 base 种情况。

算法步骤

1. 初始化 count = 0，base = 1。

2. 循环直到 base > n：

   • 计算 high、cur、low。

   • 根据 cur 的值累加 count。

   • base *= 10。

3. 返回 count。

优化算法：

class Solution:
    def countDigitOne(self, n: int) -> int:
        count=0
        base=1
        while n>=base:
            high=n//(base*10)
            cur=(n//base)%10
            low=n%base
            match cur:
                case 0:
                    count+=high*base
                case 1:
                    count+=high*base+low+1
                case _:
                    count+=(high+1)*base
            base*=10
        return count

📊 性能分析

提交结果

• 运行时间：0ms击败100.00%
• 内存消耗：17.48MB击败71.54%

复杂度验证

• 时间复杂度：$O(log(n))$
• 空间复杂度：$O(1)$