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

1. 问题引入一个看似简单却暗藏玄机的计数问题在编程面试或者算法练习中我们经常会遇到一些关于数字统计的问题。今天要讨论的这个——“1n 整数中 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’的个数通常有两种方法字符串转换法将整数i转换为字符串遍历字符串的每个字符若字符为‘1’则计数加一。数学取位法不断对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)。当n1,000,000,000十亿时这个计算量是巨大的在实际应用或在线判题系统中很容易超时。为什么面试官不喜欢这个答案因为它没有展示出任何对问题本质的洞察和优化能力。它仅仅是将问题的描述翻译成了代码。在工程中对于小规模数据这没问题但算法题往往考察的就是处理大规模数据的高效方法。所以我们必须找到更优解。2.2 寻找模式启发于具体的例子在寻求数学解法前我们先手动计算一些小例子观察规律。设函数f(n)为题目所求。f(1) 1f(9) 1 只有数字1f(10) 2 数字1和10的十位f(11) 4 数字1 10的十位 11的十位和个位—— 这里需要注意11含有两个‘1’。f(13) 6 1, 10, 11, 12, 13。其中11贡献两个其余各贡献一个共112116f(20) 12f(99) 20f(100) 21仅仅从这些离散的结果很难看出通用公式。我们需要换一个视角不按数字来统计而是按数位来统计。即分别计算个位上出现1的次数、十位上出现1的次数、百位上出现1的次数……最后将它们加起来。这个视角转换是解决本题的关键突破点。因为同一个数字在不同位上出现‘1’的规律是相对独立且可循的。3. 核心思路按位计数与“当前位”分析法我们不再考虑完整的数字而是聚焦于某一个特定的“位”比如十位思考在1n的所有数字中这个位上的数字为1的情况出现了多少次。以n3101592为例我们来分析百位从右向左数第三位记作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比如n3101092我们把原数的百位改成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。 对应到原数n3101592cur9不是0此情况不适用。但我们可以想象如果计算的是千位cur1当千位为0时公式就是high * 1000。3.2 情况二当前位数字等于1 (cur 1)如果当前位是1比如n3101192。那么情况比等于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比如我们原例的cur9。那么情况最为“宽松”。 百位为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我们计算high n // (factor * 10)cur (n // factor) % 10low 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。以n3101592计算百位(factor100)为例high 3101592 // 1000 3101cur (3101592 // 100) % 10 9low 3101592 % 100 92因为cur9 1所以百位贡献的1的个数 (3101 1) * 100 310200。我们需要对每一位个、十、百、千、万、十万、百万都执行这个过程并将结果累加。4. 算法实现与逐位演算理解了核心公式实现起来就非常清晰了。我们以n3101592为例手动演算一遍整个过程并给出代码。初始化count 0,factor 1循环开始个位(factor1):high 3101592 // 10 310159cur (3101592 // 1) % 10 2low 3101592 % 1 0cur2 1-count (310159 1) * 1 310160十位(factor10):high 3101592 // 100 31015cur (3101592 // 10) % 10 9low 3101592 % 10 2cur9 1-count (31015 1) * 10 310160累计count 310160 310160 620320百位(factor100):high 3101592 // 1000 3101cur (3101592 // 100) % 10 9low 3101592 % 100 92cur9 1-count (3101 1) * 100 310200累计count 620320 310200 930520千位(factor1000):high 3101592 // 10000 310cur (3101592 // 1000) % 10 1low 3101592 % 1000 592cur1-count high * factor low 1 310 * 1000 592 1 310593累计count 930520 310593 1241113万位(factor10000):high 3101592 // 100000 31cur (3101592 // 10000) % 10 0low 3101592 % 10000 1592cur0-count high * factor 31 * 10000 310000累计count 1241113 310000 1551113十万位(factor100000):high 3101592 // 1000000 3cur (3101592 // 100000) % 10 1low 3101592 % 100000 101592cur1-count high * factor low 1 3 * 100000 101592 1 401593累计count 1551113 401593 1952706百万位(factor1000000):high 3101592 // 10000000 0cur (3101592 // 1000000) % 10 3low 3101592 % 1000000 101592cur3 1-count (high 1) * factor (01) * 1000000 1000000累计count 1952706 1000000 2952706循环结束(因为下一个factor10000000 n)。所以最终结果f(3101592) 2952706。代码实现如下Pythondef 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 (根据题意10没有数字应为0)时间复杂度循环的次数等于数字n的位数即O(log₁₀ n)。这是一个非常高效的算法。空间复杂度O(1)只使用了常数个变量。5. 边界处理、常见错误与思维延伸5.1 边界条件与细节陷阱n0的情况题目是“1n”当n0时区间内没有整数结果应为0。我们的算法中while factor n循环条件一开始就不满足count保持为0结果正确。n为负数的情况通常题目约定n是非负整数或正整数。如果考虑负数情况会复杂很多例如-1到-10中‘1’出现在负号还是数字。一般算法题中不做考虑若遇到需明确题意。整数溢出在诸如C、Java等语言中需要注意factor * 10可能溢出。通常的解决方法是使用长整型(long long)或者在循环条件中用n / factor 0来判断。Python整数无此问题。cur、high、low的计算顺序务必先计算high和low再更新factor。因为high和low的计算依赖于当前的factor。low 1的含义在cur1的情况下low 1代表低位从0到low共有low1种取法。这是非常容易漏掉1的地方。5.2 为什么是“1”而不是其他数字我们深入思考一下这个方法是否只适用于统计‘1’其实不然。这个按位分析的方法具有普适性。如果我们想统计1n中数字‘k’1≤k≤9出现的次数公式几乎完全一样只需要在判断cur时与k比较即可。统计数字k1~9出现次数的通用公式 对于每一位因子factorhigh n // (factor * 10)cur (n // factor) % 10low 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下的运行时间单位秒。n的规模暴力解法耗时数学解法耗时速度提升倍数10^5 (100,000)~0.15秒0.00001秒 10,000倍10^6 (1,000,000)~1.5秒0.00001秒 150,000倍10^7 (10,000,000)~15秒0.00001秒 1,500,000倍10^9 (1,000,000,000)预计超时(1000秒)0.00001秒无法估量注意实际耗时因机器性能而异但数量级差异是绝对的。对于10^9暴力解法在常规环境下几乎不可能在合理时间内完成。这道“1的个数”问题堪称是检验程序员思维深度的试金石。它教会我的最重要一点是面对一个清晰描述的问题第一反应不应该是立刻动手写代码而是先问自己“数据的规模有多大”和“有没有更本质的规律”。暴力解法是思维的舒适区它直接、正确但往往低效。而高效的算法通常需要我们跳出问题的表面叙述进行抽象、分解和归纳。这道题将“数字计数”分解为“数位计数”就是一次完美的抽象。在平时的工作和刷题中养成这种“分解与抽象”的思维习惯至关重要。比如处理字符串匹配时想到哈希或自动机处理区间查询时想到前缀和或树状数组其本质都是通过改变数据视图或预处理将原问题转化为更容易高效解决的新问题。另一个体会是关于分类讨论的严谨性。在推导公式时cur等于0、1、大于1这三种情况必须划分清楚每种情况下的计数逻辑high能取多少low能取多少必须丝毫不差。这锻炼了严密的逻辑思维能力。在实现时我建议像本文一样先用一个具体的数字如3101592手动算一遍验证自己推导的公式和代码逻辑是否正确这比干想和直接写代码要可靠得多。