如何优化Python中统计1到n间数字含9个数的代码？

原代码的问题很明显：当n特别大时，要把1到n的每一个数字转成字符串，再逐个统计含9的次数，时间复杂度是O(n)，数字越多越慢，直接触发超时。

换用数学计数法就能彻底解决这个问题，不用遍历每个数字，而是按数位计算每个位置上9出现的总次数，时间复杂度降到O(log₁₀n)，不管n多大都能秒出结果。

核心思路 #

对每个数位（个位、十位、百位……），分三种情况计算该数位上9出现的次数：

• 若当前位数字小于9：该数位上9出现的次数 = 高位数字 × 当前位的位权（比如百位的位权是100）
• 若当前位数字等于9：次数 = 高位数字 × 位权 + 低位数字 + 1
• 若当前位数字大于9：次数 = (高位数字 + 1) × 位权

把所有数位的结果相加，就是1到n中所有数字里9的总个数。

优化后的代码 #

def count_nines(n):
    count = 0
    digit_place = 1  # 从个位开始计算，位权初始为1
    while digit_place <= n:
        # 拆分出高位、当前位、低位数字
        higher = n // (digit_place * 10)
        current = (n // digit_place) % 10
        lower = n % digit_place
        
        # 根据当前位数字的情况累加次数
        if current < 9:
            count += higher * digit_place
        elif current == 9:
            count += higher * digit_place + lower + 1
        else:
            count += (higher + 1) * digit_place
        
        # 移动到下一个更高的数位
        digit_place *= 10
    return count

效果对比 #

• 原代码：n=10^9时，需要遍历10亿个数字，必然超时
• 优化后代码：n=10^18时，只需要遍历18次数位，瞬间得到结果

内容的提问来源于stack exchange，提问作者test