2026-07-08统计区间内奇妙数的数目。用go语言给定一个正整数 n我们要考虑从 1 到 n 之间包括 1 和 n的所有整数。对每个数按照常见的千位分隔习惯写成字符串从个位开始向左数每三位插入一个逗号但如果这个数不足四位也就是小于 1000则不加任何逗号。问题是把 1 到 n 这 n 个数的这种书写形式连起来看总共出现了多少个逗号请计算出这个总数。1 n 100000。输入 n 1002。输出 3。解释数字 “1,000”、“1,001” 和 “1,002” 每个都包含一个逗号总计 3 个逗号。题目来自力扣38703871。一、函数 countCommas(n int64) 分步逻辑拆解步骤1定义变量kk代表每个数字固定拥有的逗号个数档位k 是完整千位段的数量对应数字统一携带的逗号数量数字区间 [10^(3m), 10^(3m3)-1] 内所有数都固定有 m 个逗号m01~999k0无逗号m11000~999999k11个逗号m21000000~999999999k22个逗号以此类推步骤2计算k的核心逻辑2.1 特殊边界说明当 n 10^15 时浮点数 math.Log10 会存在精度丢失无法正确算出位数因此代码预设兜底 k5题目限制 n≤100000不会触发该特判仅为超大数兼容。2.2 常规n1e15时的k计算流程将整数n转为浮点数调用 math.Log10 得到n的十进制位数减1例 n1002log10(1002)≈3.000867对结果取整数得到数字总位数减1int(3.000867)3整除3得到完整千位段数量k3 / 3 1含义1002属于1000~999999区间每个数字固定1个逗号k1步骤3拆分总逗号的数学公式推导总逗号 两部分相减总逗号 k × (n 1) − 前k个完整千位区间全部数字产生的逗号总和第一部分k × (n1)假设从1到n所有数字都有k个逗号先算出理论最大值。示例 n1002k11 × (10021) 1003含义假设1~1002每个数字都带1个逗号合计1003个逗号。第二部分(10^(3k3) − 1000) / 999这一步计算1 ~ (10^(3k)-1) 所有数字实际不含k个逗号的总差值也就是需要扣除的无效逗号数量。3k完整千位段对应的位数偏移k1时 3k33k3 610^6 100000010^6 − 1000 999000除以999999000 / 999 1000含义1~999 这1000个数字本身没有1个逗号前面理论计算时给它们全部算了1个逗号多算了1000个需要全部减去。步骤4合并公式计算最终答案代入示例 n1002总逗号 1003 − 1000 3和题目输出完全匹配。通用公式数学意义k 代表当前数字档位的标准逗号数k*(n1)给1~n全部数字强制分配k个逗号得到高估总和减数项统计所有小于10^(3k)的数字总个数这些数字本身不足k个逗号全部是多算的部分需要扣除相减后得到真实总逗号数量。步骤5main函数执行流程定义输入n1002转为int64类型传入countCommas执行上述数学计算得到结果打印输出最终逗号总数。二、整体算法核心思想总结不暴力遍历1~n逐个统计避免循环利用十进制千位分段数学公式直接计算按数字所在区间批量统计逗号先确定当前数字所在千位分段得到该分段标准逗号数k用整体高估法统一给所有数字分配k个逗号减去低位区间不足k个逗号的数字总数修正高估误差一步算出总逗号无循环、无逐一枚举。三、时间复杂度 额外空间复杂度分析1. 时间复杂度 O(1)整个计算仅执行常数次数学运算log10、整数转换、幂运算、四则加减乘除不存在循环、递归、遍历操作运算次数不随n的大小变化固定常数次计算时间复杂度为常量级 O(1)。2. 额外空间复杂度 O(1)函数内部仅定义固定数量局部变量k、ans无动态数组、切片、哈希、递归栈等动态内存分配的内存空间大小与输入n无关始终为固定常量空间额外空间复杂度 O(1)。Go完整代码如下packagemainimport(fmtmath)funccountCommas(nint64)(ansint64){k:5// n 1e15 时 Log10(n) 有误差需要特判ifn1e15{kint(math.Log10(float64(n)))/3}returnint64(k)*(n1)-(int64(math.Pow10(k*33))-1000)/999}funcmain(){n:1002result:countCommas(int64(n))fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defcount_commas(n:int)-int: 返回从 1 到 n含所有整数的标准书写格式中逗号的总数 ifn1000:return0# k 表示最高位的逗号组数例如 n1000 时 k1n1_000_000 时 k2k(len(str(n))-1)//3# 使用公式k*(n1) - (10^(3k3) - 1000) / 999pow1010**(3*k3)returnk*(n1)-(pow10-1000)//999if__name____main__:n1002resultcount_commas(n)print(result)C完整代码如下#includeiostream#includecmath#includecstdintint64_tcountCommas(int64_tn){intk5;// 当 n 1e15 时直接取 5避免 log10 的精度误差constexprint64_tthreshold1000000000000000LL;// 1e15if(nthreshold){kstatic_castint(std::log10(static_castdouble(n)))/3;}int64_tpow10static_castint64_t(std::pow(10.0,k*33));returnstatic_castint64_t(k)*(n1)-(pow10-1000)/999;}intmain(){int64_tn1002;int64_tresultcountCommas(n);std::coutresultstd::endl;return0;}
