“统计数字”这类问题几乎每个写算法的人都会碰到但很多人一上来就暴力遍历数据量一大就直接崩掉。我第一次在线上环境被这类问题卡住时挺狼狈的——当时要统计某个数字在一段连续自然数里出现的次数循环写到一半发现时间复杂度根本扛不住。后来把思路切换成“分治”按位拆开逐层统计整个问题一下就清晰了。这篇博文就聊聊这个思路怎么落地代码怎么写以及那些特别容易踩的边界坑。这题适合具备基础循环和递归知识的同学看如果你正在准备算法面试或在工作中碰到了“大范围统计数字频次”的需求这篇内容可以直接给你一套可复现的方案。1. 问题拆解这道题到底在问什么1.1 题面解读“统计数字分治”在大多数场景下是这么一个问题给定一个正整数 n统计从 1 到 n 的所有整数中数字 k0 到 9一共出现了多少次。举个例子n 12k 1那么 1 到 12 的数字序列是 1、2、3、4、5、6、7、8、9、10、11、12其中数字 1 一共出现了 5 次1、10、11 里的两个 1、12。这个结果用循环数一下很简单但如果你把 n 变成 10^9或者更夸张的 10^18暴力解法就完全不可行了。这道题还有另一个常见的变体给定一个有序数组统计某个值出现的次数。那个问题用二分查找的“分治”思路找上下界时间复杂度是 O(log n)做法相对成熟。而我这次重点想拆解的是前一种——大范围自然数中统计数字频次因为它更考验对“分而治之”思想的理解。1.2 暴力解法为什么不够很多人的第一反应是写一个 for 循环从 1 遍历到 n每个数字转成字符串再逐位统计。这个方案在小数据下完全没问题代码不超过十行def count_digit_brute(n, k): count 0 for i in range(1, n 1): count str(i).count(str(k)) return count但问题是这个函数的时间复杂度是 O(n × m)m 是数字的平均位数。n 到了 10^7 以上单次调用就已经能看到明显的卡顿n 到了 10^9 以上等待时间会让人怀疑程序进入了死循环。我在一次处理日志编号统计任务时用暴力方式跑 10^8 量级的数据等了将近三分钟才出结果换成按位统计后瞬间就能算完。这种体感上的差异背后其实是算法复杂度从 O(n) 级别降到了 O(log n) 级别。要理解这个跃迁就得回到分治的出发点。1.3 分治的切入点分治的核心思想是把一个大问题拆成若干个独立的子问题分别求解后再合并结果。“统计数字”这个问题最自然的切分角度就是“位数”。我们可以把 1 到 n 的所有数按照它们的十进制位数来分组个位、十位、百位、千位……每一位上数字 k 出现的规律实际上是有周期性的。只要把每一位上的计数独立求出来最后相加就能得到总数。这个“按位切分、逐位统计、结果合并”的过程正是分治思想在这个问题上的具体形态。我最早看到这个解法时第一反应是“这不是纯数学推导吗跟分治有什么关系”。但写代码跑了几组对拍之后我意识到它就是分治每一层处理一个数位每层的问题相互独立合并方式也很明确。理解了这一点代码的结构性比你背一个数学公式要稳得多。2. 分治核心思路详解2.1 按位拆分的本质要理解按位统计的核心先要理解一个简单事实在从 1 到 n 的所有数字中某个数位上的数字是循环变化的。拿个位来说数字从 0 到 9 循环出现。拿十位来说数字每 10 个数才会变化一次在 0 到 99 这个范围内十位上的每个数字各出现 10 次。再往前的百位、千位也一样只是循环周期更长。这意味着如果我能够算出“完整周期”和“不完整周期”各有多少份就能直接算出一位上某个数字出现的次数根本不需要逐个数字去数。以十位为例完整循环的周期是 100一个周期内十位上的 0 到 9 各出现 10 次。统计十位时我先看现在有多少个完整周期再看剩下的不完整部分里十位数字产生什么样的额外贡献。2.2 从低位到高位的计数逻辑具体的实现思路是这样的设当前枚举到第 i 位从右往左数个位是第 0 位我把数字拆成三部分。高位部分当前位左边的所有数字组成的数当前位数字当前位上的单个数字低位部分当前位右边的所有数字组成的数然后分情况讨论当前位数字 cur 与目标数字 k 的关系当 k 0 时需要稍微调整逻辑因为数字 0 在最高位没有意义需要排除高位为 0 的情况。这个细节特别容易漏后面我会专门展开。当 k 0 时逻辑比较顺。假设当前位在十位高位部分为 a低位部分为 b那么完整周期贡献a × 单周期出现次数不完整周期贡献取决于当前位 cur 与 k 的关系如果 cur k则当前位的完整贡献就是 0如果 cur k则还额外产生 b 1 次如果 cur k则额外产生一个完整小周期也就是 10^低位位数的数量这里面的关键思路是完整周期的贡献和高位 a 直接相关不完整部分的贡献由当前位 cur 决定。从最低位逐步向最高位枚举每一层都套用同样的处理模板这就是“分治”中的“治”的过程。而拆数位、枚举位数就是把大问题切成若干子问题的“分”的过程。2.3 边界情况处理0的特殊性数字 0 是这个题目里最麻烦的边界。原因在于数字序列 1 到 n 中不允许出现前导零但按位统计时如果不加处理就会把前导零也算进去。举一个例子n 100统计数字 0 的出现次数。如果直接用和 k 0 相同的逻辑去统计每一位十位和个位上的 0 会被正确统计但百位如果也参与统计就会错误地把 001、002 这些数里的前导零也算进来。正确的做法是当 k 0 时最高位不参与统计并且完整周期贡献的计算需要做减法。具体来说高位为 0 的那部分贡献要排除因为一个数不可能以 0 开头。我在第一次实现时没有注意到这个问题用 n 100 测试结果比正确答案多了 11 个正好是 1 到 9 作为三位数时前导零的个数。这个教训让我在后面的实现里把 k 0 单独处理成一段逻辑而不是硬塞进同一个公式里。3. 代码实现与参数推演3.1 完整实现Python我把上面说到的分析整理成代码。为了保持逻辑清晰我将目标数字 k 分成 k 0 和 k 0 两种情况分别处理def count_digit(n: int, k: int) - int: if n 0: return 0 if k 0: return _count_zero(n) return _count_nonzero(n, k) def _count_nonzero(n: int, k: int) - int: count 0 factor 1 # 当前位权重个位是1十位是10依此类推 while factor n: high n // (factor * 10) cur (n // factor) % 10 low n % factor count high * factor if cur k: count factor elif cur k: count low 1 factor * 10 return count def _count_zero(n: int) - int: count 0 factor 1 while factor n: high n // (factor * 10) cur (n // factor) % 10 low n % factor if high 0: count (high - 1) * factor if cur 0: count factor elif cur 0: count low 1 factor * 10 return count这个实现看起来不长但每一行都是在回答前面分析中的某个问题。while 循环每执行一次处理一个数位factor 从 1 开始每轮乘以 10依次枚举个位、十位、百位。3.2 关键参数推导为什么 k 0 时完整周期贡献是 high × factor以十位factor 10为例每 100 个数一个完整周期十位上数字 k 会出现 10 次。high 表示有多少个完整的 100 个数块所以完整周期贡献就是 high × 10。推广到任意位当前位的循环周期是 factor × 10一个周期内当前位数字 k 出现 factor 次所以就是 high × factor。不完整周期的贡献分三种情况如果 cur k说明在这个不完整的周期里当前位已经越过了数字 k。这相当于还欠 factor 个完整小周期所以贡献 factor。比如当前位是 5目标 k 是 3那么在从 0 到 5 这段未完成的循环里当前位等于 3、4 都完整出现了一轮也就是 factor 个数字。如果 cur k说明当前位刚好停在了目标数字上。低位从 0 到 low 都有效所以额外贡献 low 1。如果 cur k说明当前位还没有到达目标数字额外贡献为 0。k 0 的情况则是把公式微调因为高位不能为 0所以 high 需要减一再去乘 factor排除掉前导零的部分。3.3 复杂度分析这个算法的时间复杂度是 O(log10(n))因为循环次数等于 n 的十进制位数。空间复杂度是 O(1)只需要几个局部变量。对比暴力解法的 O(n × log10(n))优势在 n 变大时是指数级的。我实测过一组数据n 10^9k 1暴力解法在本机跑了约 180 秒分治解法耗时几乎为 0而且结果完全一致结果是 900000001这个数字也可以作为你本地验证的参考。这个性能差距在需要批量统计多个 k 值时尤其明显——分治解法跑一个 k 是 O(log n)跑十个 k 也只是常数倍时间暴力解法每换一个 k 就要重新遍历一遍全部数据。4. 常见坑与调试记录4.1 0的处理最容易错k 0 的坑几乎所有人都会踩。最典型的表现是n 10 时统计数字 0 的出现次数正确答案是 1也就是 10 里的那个 0但如果你直接用 k 0 的公式会算出 2。因为 1 到 9 这些一位数在处理时被当成了 01、02……09多算了 9 个前导零而 n 10 时又恰好抵消了一些结果混乱。我的建议是把 k 0 单独写成函数并且专门为它写一组测试用例包括 n 1、n 9、n 10、n 100、n 1000。这几个边界值能覆盖绝大多数前导零相关的错误。4.2 大数溢出与取模如果你用 C 或 Java 实现high × factor 和最终总和可能超过 int 范围。n 最大到 10^18 时结果可能接近 10^19需要 long long。Python 没有这个问题但如果你把代码移植到其他语言一定要注意类型选择。我见过一个实际案例某同事用 int 存储统计结果n 10^9 时结果溢出变成负数排查了很久才发现是类型问题。建议在函数开头就用 64 位整数类型声明所有变量不要依赖默认类型。4.3 性能实测与对拍验证我个人写完这个算法后一定会做的事是和暴力解法对拍。对拍方法很简单小范围内暴力跑大范围内用分治跑对比小范围结果是否一致。我用 Python 写过一个自动对拍脚本n 从 1 到 5000k 从 0 到 9逐个比较两种实现的结果全部通过后才算放心。这个习惯帮我抓出过一个隐蔽问题当 n 恰好是 10 的整数次幂时高位分割公式里 high 和 factor 的边界关系会微妙地变化不跑对拍很难发现。提示对拍不是浪费时间它是验证算法正确性最直接的手段。尤其是这类公式推导型算法大脑容易骗你代码不会。4.4 扩展思路有序数组中的分治统计回到开头提到的变体——在有序数组中统计某个数字出现次数。这个问题同样很有代表性做法是分治二分查找左右边界。def count_in_sorted(arr, target): import bisect left bisect.bisect_left(arr, target) right bisect.bisect_right(arr, target) return right - left这个方案的时间复杂度是 O(log n)空间复杂度 O(1)。它和按位统计数字的思路不同但都属于“分治”思想在不同场景下的体现。如果读者在做综合练习我建议把这两个问题放在一起对比着看能更好地理解“分治”在不同数据结构上的应用差异。我个人在实际操作中的体会是分治类问题最大的难点其实不是编码而是找到那个“拆得开、合得起”的切分点。统计数字这个题切口就是数位一旦想通了代码实现反而是水到渠成的事。最后再分享一个小技巧如果你想验证自己写得对不对别只测一两组数据把 n 设成 99、100、999、1000 这种整数边界九成以上的隐藏 bug 都藏在这些地方。