从暴力到高效：数位统计法求解1～n整数中1出现的次数

1. 问题引入：一个看似简单却暗藏玄机的计数问题

在编程面试或者算法练习中，我们经常会遇到一些关于数字统计的问题。今天要讨论的这个——“1～n 整数中 1 出现的次数”——就是其中非常经典，也极具迷惑性的一道。乍一看，这题目简单得过分：不就是从1数到n，看看每个数字里有多少个‘1’，然后加起来吗？写个循环，把每个数字转成字符串数一数，或者不断模10取个位数判断，不就解决了？

没错，暴力解法（Brute Force）确实直观。但如果你在面试中只给出这个答案，或者在实际处理一个巨大的n（比如10的9次方）时还这么干，那结果很可能不太美妙。暴力解法的时间复杂度是O(n * log₁₀ n)，当n很大时，计算量会急剧膨胀，导致程序运行缓慢甚至超时。这道题真正的价值，或者说面试官想考察的，绝不是你会不会写循环，而是你能否跳出直观思维的陷阱，去发现数字规律，并设计出高效的数学解法。

它本质上是一个数位统计问题，核心在于如何避免逐个检查每个数字，而是通过分析数字的结构，直接计算出最终结果。这需要我们对十进制数的位值有清晰的认识，并运用一些巧妙的分类讨论和数学归纳思想。接下来，我们就一起拆解这个问题，看看如何从最笨的方法出发，一步步推导出那个优雅且高效的O(log n)解法。

2. 从暴力破解到寻求突破：理解问题的规模陷阱

我们先从最直接的方法开始，这能帮助我们彻底理解问题，并明确优化的必要性。

2.1 暴力解法的实现与局限

暴力解法的思路非常直白：遍历从1到n的每一个整数i，统计i的十进制表示中数字‘1’出现的次数，然后累加。

统计一个数字i中‘1’的个数，通常有两种方法：

1. 字符串转换法：将整数i转换为字符串，遍历字符串的每个字符，若字符为‘1’则计数加一。
2. 数学取位法：不断对i进行i % 10操作获取个位数，判断是否为1，然后通过i /= 10去掉个位，直到i变为0。

数学取位法效率稍高，因为它避免了字符串转换的开销。我们用代码表示如下（以Python为例）：

def count_digit_one_bruteforce(n: int) -> int: count = 0 for i in range(1, n + 1): while i > 0: if i % 10 == 1: count += 1 i //= 10 # 注意：这里会改变循环变量i，在实际实现中需要用临时变量 return count # 更严谨的实现，使用临时变量 def count_digit_one_bruteforce_correct(n: int) -> int: total_count = 0 for i in range(1, n + 1): num = i while num > 0: if num % 10 == 1: total_count += 1 num //= 10 return total_count

时间复杂度分析：外层循环遍历n次，内层循环对于每个数字i，其循环次数等于i的位数，即大约log₁₀ i次。因此，总的时间复杂度可以粗略估计为O(n log n)。当n=1,000,000,000（十亿）时，这个计算量是巨大的，在实际应用或在线判题系统中很容易超时。

为什么面试官不喜欢这个答案？因为它没有展示出任何对问题本质的洞察和优化能力。它仅仅是将问题的描述翻译成了代码。在工程中，对于小规模数据这没问题，但算法题往往考察的就是处理大规模数据的高效方法。所以，我们必须找到更优解。

2.2 寻找模式：启发于具体的例子

在寻求数学解法前，我们先手动计算一些小例子，观察规律。设函数f(n)为题目所求。

• f(1) = 1
• f(9) = 1 （只有数字1）
• f(10) = 2 （数字1和10的十位）
• f(11) = 4 （数字1， 10的十位， 11的十位和个位）—— 这里需要注意，11含有两个‘1’。
• f(13) = 6 （1, 10, 11, 12, 13。其中11贡献两个，其余各贡献一个，共1+1+2+1+1=6）
• f(20) = 12
• f(99) = 20
• f(100) = 21

仅仅从这些离散的结果很难看出通用公式。我们需要换一个视角：不按数字来统计，而是按数位来统计。即，分别计算个位上出现1的次数、十位上出现1的次数、百位上出现1的次数……最后将它们加起来。

这个视角转换是解决本题的关键突破点。因为同一个数字在不同位上出现‘1’的规律是相对独立且可循的。

3. 核心思路：按位计数与“当前位”分析法

我们不再考虑完整的数字，而是聚焦于某一个特定的“位”（比如十位），思考在1～n的所有数字中，这个位上的数字为1的情况出现了多少次。

以n=3101592为例，我们来分析百位（从右向左数第三位，记作digit位）上出现1的次数。我们把数字拆成三部分：高位high、当前位cur、低位low。

• 记当前位的位置因子为factor = 100(因为百位)。
• 则high = n // (factor * 10) = 31015(即百位之前的部分)
• cur = (n // factor) % 10 = 9(即百位上的数字)
• low = n % factor = 92(即百位之后的部分)

现在，问题转化为：在0到3101592之间，百位数字为1的数有多少个？我们可以根据当前位cur的值分三种情况讨论：

3.1 情况一：当前位数字等于0 (cur == 0)

如果当前位是0，比如n=3101092（我们把原数的百位改成0），那么百位为1的数字范围完全由高位决定。 百位为1的数字形如：[high]1[low]，其中low可以从00取到99。 那么有多少个呢？high部分固定，low部分有100种可能（0到99）。所以，百位为1的数字个数 =high * factor。为什么？因为高位high可以从0取到(high-1)，共high种可能。对于每一种高位，低位都有factor（这里是100）种可能。所以是high * 100。 对应到原数n=3101592，cur=9不是0，此情况不适用。但我们可以想象，如果计算的是千位（cur=1），当千位为0时，公式就是high * 1000。

3.2 情况二：当前位数字等于1 (cur == 1)

如果当前位是1，比如n=3101192。那么情况比等于0时复杂一些。 百位为1的数字形如同样为：[high]1[low]。但此时，high部分不能随意取了，因为它受到整体数字不能超过n的限制。

• 当高位取0 到 high-1时，低位low可以任意取0 到 factor-1（即0到99）。这部分贡献了high * factor个数字。
• 当高位取high时（即和n的高位相同），低位low只能取0 到 low（即0到92），否则整体数字就会超过n。这部分贡献了low + 1个数字。 所以，总次数 =high * factor + (low + 1)。

3.3 情况三：当前位数字大于1 (cur > 1)

如果当前位大于1，比如我们原例的cur=9。那么情况最为“宽松”。 百位为1的数字形如：[high]1[low]。

• 高位high可以取0 到 high（注意，这里可以取到high本身，因为即使高位和n一样，当前位是1也肯定小于9，所以整个数不会超过n）。这部分有high + 1种可能。
• 对于每一种高位，低位low都可以任意取0 到 factor-1（即0到99）。有factor种可能。 所以，总次数 =(high + 1) * factor。

3.4 公式归纳与计算过程

我们将上述三种情况统一起来，对于从个位开始到最高位的每一位（设位置因子为factor，初始为1，每次循环乘以10），我们计算：

1. high = n // (factor * 10)
2. cur = (n // factor) % 10
3. low = n % factor然后根据cur的值累加结果：

• 若cur == 0:count += high * factor
• 若cur == 1:count += high * factor + low + 1
• 若cur > 1:count += (high + 1) * factor最后，factor *= 10，继续处理下一位，直到factor > n。

以n=3101592，计算百位(factor=100)为例：

• high = 3101592 // 1000 = 3101
• cur = (3101592 // 100) % 10 = 9
• low = 3101592 % 100 = 92
• 因为cur=9 > 1，所以百位贡献的1的个数 =(3101 + 1) * 100 = 310200。

我们需要对每一位（个、十、百、千、万、十万、百万）都执行这个过程，并将结果累加。

4. 算法实现与逐位演算

理解了核心公式，实现起来就非常清晰了。我们以n=3101592为例，手动演算一遍整个过程，并给出代码。

初始化：count = 0,factor = 1

循环开始：

1. 个位(factor=1):

   • high = 3101592 // 10 = 310159
   • cur = (3101592 // 1) % 10 = 2
   • low = 3101592 % 1 = 0
   • cur=2 > 1->count += (310159 + 1) * 1 = 310160

2. 十位(factor=10):

   • high = 3101592 // 100 = 31015
   • cur = (3101592 // 10) % 10 = 9
   • low = 3101592 % 10 = 2
   • cur=9 > 1->count += (31015 + 1) * 10 = 310160
   • 累计count = 310160 + 310160 = 620320

3. 百位(factor=100):

   • high = 3101592 // 1000 = 3101
   • cur = (3101592 // 100) % 10 = 9
   • low = 3101592 % 100 = 92
   • cur=9 > 1->count += (3101 + 1) * 100 = 310200
   • 累计count = 620320 + 310200 = 930520

4. 千位(factor=1000):

   • high = 3101592 // 10000 = 310
   • cur = (3101592 // 1000) % 10 = 1
   • low = 3101592 % 1000 = 592
   • cur==1->count += high * factor + low + 1 = 310 * 1000 + 592 + 1 = 310593
   • 累计count = 930520 + 310593 = 1241113

5. 万位(factor=10000):

   • high = 3101592 // 100000 = 31
   • cur = (3101592 // 10000) % 10 = 0
   • low = 3101592 % 10000 = 1592
   • cur==0->count += high * factor = 31 * 10000 = 310000
   • 累计count = 1241113 + 310000 = 1551113

6. 十万位(factor=100000):

   • high = 3101592 // 1000000 = 3
   • cur = (3101592 // 100000) % 10 = 1
   • low = 3101592 % 100000 = 101592
   • cur==1->count += high * factor + low + 1 = 3 * 100000 + 101592 + 1 = 401593
   • 累计count = 1551113 + 401593 = 1952706

7. 百万位(factor=1000000):

   • high = 3101592 // 10000000 = 0
   • cur = (3101592 // 1000000) % 10 = 3
   • low = 3101592 % 1000000 = 101592
   • cur=3 > 1->count += (high + 1) * factor = (0+1) * 1000000 = 1000000
   • 累计count = 1952706 + 1000000 = 2952706

循环结束(因为下一个factor=10000000 > n)。

所以，最终结果f(3101592) = 2952706。

代码实现如下（Python）：

def count_digit_one_math(n: int) -> int: count = 0 factor = 1 while factor <= n: high = n // (factor * 10) cur = (n // factor) % 10 low = n % factor if cur == 0: count += high * factor elif cur == 1: count += high * factor + low + 1 else: # cur > 1 count += (high + 1) * factor factor *= 10 return count # 测试 print(count_digit_one_math(3101592)) # 输出: 2952706 print(count_digit_one_math(13)) # 输出: 6 print(count_digit_one_math(0)) # 输出: 0 (根据题意，1～0没有数字，应为0)

时间复杂度：循环的次数等于数字n的位数，即O(log₁₀ n)。这是一个非常高效的算法。空间复杂度：O(1)，只使用了常数个变量。

5. 边界处理、常见错误与思维延伸

5.1 边界条件与细节陷阱

1. n=0的情况：题目是“1～n”，当n=0时，区间内没有整数，结果应为0。我们的算法中，while factor <= n循环条件一开始就不满足，count保持为0，结果正确。
2. n为负数的情况：通常题目约定n是非负整数或正整数。如果考虑负数，情况会复杂很多（例如-1到-10中‘1’出现在负号还是数字？）。一般算法题中不做考虑，若遇到需明确题意。
3. 整数溢出：在诸如C++、Java等语言中，需要注意factor * 10可能溢出。通常的解决方法是使用长整型(long long)，或者在循环条件中用n / factor > 0来判断。Python整数无此问题。
4. cur、high、low的计算顺序：务必先计算high和low，再更新factor。因为high和low的计算依赖于当前的factor。
5. low + 1的含义：在cur==1的情况下，low + 1代表低位从0到low共有low+1种取法。这是非常容易漏掉+1的地方。

5.2 为什么是“1”而不是其他数字？

我们深入思考一下，这个方法是否只适用于统计‘1’？其实不然。这个按位分析的方法具有普适性。如果我们想统计1～n中数字‘k’（1≤k≤9）出现的次数，公式几乎完全一样，只需要在判断cur时与k比较即可。

统计数字k（1~9）出现次数的通用公式： 对于每一位（因子factor）：

• high = n // (factor * 10)
• cur = (n // factor) % 10
• low = n % factor
• 若cur < k:count += high * factor
• 若cur == k:count += high * factor + low + 1
• 若cur > k:count += (high + 1) * factor

那么统计数字0呢？统计0会稍微特殊一些，因为数字的最高位不能是0。我们需要在通用公式的基础上，对最高位的情况进行特殊处理，或者从统计“非零数字”的角度反向计算。这可以作为一道很好的延伸思考题。

5.3 从数位动态规划（Digit DP）的角度理解

本题的数学解法，其思想内核与数位动态规划（Digit DP）高度相关。Digit DP常用于解决“在某个区间内，满足特定条件的数字有多少个”这类问题。我们的“按位计数”法，可以看作是Digit DP思想的一种特化和简化。

我们把问题定义为：统计[1, n]范围内，所有数字的每一位上出现1的次数之和。这个过程，实际上是在n的上限约束下，逐位决策（当前位是0、1、还是其他数字），并累加符合条件（当前位为1）的决策路径所对应的数字个数。我们推导出的公式，本质上是对这个动态规划过程的状态转移进行了数学上的封闭形式求解，从而得到了O(log n)的极致效率。

理解这种联系，有助于你解决更复杂的数位统计问题。当你面对诸如“统计区间内数字和等于S的数”、“统计不含‘4’的数字”等问题时，可以尝试套用Digit DP的模板，其状态设计通常包括：当前处理到第几位、是否已经小于上限（is_limit）、前导零处理等。

6. 实战对比与心得感悟

最后，我们来直观感受一下高效算法的威力，并分享一些从这道题中获得的体会。

我写了一个简单的测试脚本，对比暴力解法和数学解法在不同规模n下的运行时间（单位：秒）。

注意：实际耗时因机器性能而异，但数量级差异是绝对的。对于10^9，暴力解法在常规环境下几乎不可能在合理时间内完成。

这道“1的个数”问题，堪称是检验程序员思维深度的试金石。它教会我的最重要一点是：面对一个清晰描述的问题，第一反应不应该是立刻动手写代码，而是先问自己“数据的规模有多大？”和“有没有更本质的规律？”。

暴力解法是思维的舒适区，它直接、正确，但往往低效。而高效的算法通常需要我们跳出问题的表面叙述，进行抽象、分解和归纳。这道题将“数字计数”分解为“数位计数”，就是一次完美的抽象。在平时的工作和刷题中，养成这种“分解与抽象”的思维习惯至关重要。比如，处理字符串匹配时想到哈希或自动机，处理区间查询时想到前缀和或树状数组，其本质都是通过改变数据视图或预处理，将原问题转化为更容易高效解决的新问题。

另一个体会是关于分类讨论的严谨性。在推导公式时，cur等于0、1、大于1这三种情况必须划分清楚，每种情况下的计数逻辑（high能取多少，low能取多少）必须丝毫不差。这锻炼了严密的逻辑思维能力。在实现时，我建议像本文一样，先用一个具体的数字（如3101592）手动算一遍，验证自己推导的公式和代码逻辑是否正确，这比干想和直接写代码要可靠得多。