摘要
数字 “1” 在我们的生活中无处不在，但如果让你数一数 0 到 n 之间出现了多少次 “1”，你会怎么做？是一个个遍历，还是有更聪明的方法？这篇文章会带你用 Swift 解决这个问题，而且是 超高效 的方法！
问题描述
想象一下，你在做一些数据分析，比如：
- 想统计车牌号码里 “1” 出现的次数
- 想分析某个网站用户 ID 里 “1” 的分布情况
- 研究彩票号码，看 “1” 这个数字的频率
如果 n 很小，我们还能手动数一数，但 n 一旦变大，比如 1,000,000,000，手动统计就完全不现实了。那该怎么办呢？
常见思路
最容易想到的方法是 暴力遍历：
swift">var count = 0
for i in 0...n {count += String(i).filter { $0 == "1" }.count
}
看起来没毛病，但如果 n = 1,000,000,000，代码可能要跑到明天早上。效率太低，完全不行。
有没有更快的方法？当然有！
高效解法：逐位分析
我们可以不去 一个个数 “1” 的次数，而是分析 每一位 里 “1” 的贡献，快速得出最终答案。
Swift 代码
swift">func countDigitOne(_ n: Int) -> Int {var count = 0var factor = 1var currentN = nwhile currentN > 0 {let lower = n % factor // 当前位以下的数字let digit = (n / factor) % 10 // 当前位的数字let higher = n / (factor * 10) // 当前位以上的数字if digit == 0 {count += higher * factor} else if digit == 1 {count += higher * factor + lower + 1} else {count += (higher + 1) * factor}factor *= 10currentN /= 10}return count
}
代码解析
假设 n = 3156，我们从个位开始逐位分析：
- 个位：统计
0-3156里 个位是 “1” 的情况 - 十位：统计
0-3156里 十位是 “1” 的情况 - 百位：统计
0-3156里 百位是 “1” 的情况 - 千位：统计
0-3156里 千位是 “1” 的情况
在分析某一位的贡献时，我们把 n 拆成三部分：
higher：当前位的高位部分digit：当前位的数字lower：当前位的低位部分
不同情况下：
- 如果
digit == 0，说明这一位不会贡献额外的 “1”，那么 “1” 的次数就是higher * factor - 如果
digit == 1，那么除了higher * factor这个基本贡献外，还要加上lower + 1，因为这些数字也会贡献 “1” - 如果
digit > 1，那么当前位的 “1” 贡献就是(higher + 1) * factor
这个算法的 时间复杂度是 O(log n)，比暴力遍历快得多。
示例测试及结果
swift">let solution = Solution()
print(solution.countDigitOne(13)) // 输出: 6
print(solution.countDigitOne(0)) // 输出: 0
print(solution.countDigitOne(100)) // 输出: 21
来看下具体的结果：
n = 13，出现的 “1”：1, 10, 11, 12, 13，总共 6 次n = 100，出现的 “1”：1, 10-19, 21, 31, ..., 91, 100，总共 21 次
可以看到，这个方法不仅正确，而且 快得飞起。
复杂度分析
- 时间复杂度：O(log n)，因为我们按 位数 进行计算，每次循环去掉一位数字
- 空间复杂度：O(1)，只用了几个整数变量，没开额外的数组或数据结构
总结
这道题的核心是 逐位拆解法，不用一个个数 “1”，而是分析每一位对结果的贡献，从而大幅提高计算效率。
这个方法适用于 大规模数字统计 场景，比如：
- 统计电话号码、身份证号等数据里的 “1”
- 研究彩票、车牌号码里某个数字的分布
- AI 数据分析，看看某些 ID 里 “1” 出现的概率
如果你以后遇到类似的 大数据统计问题，不妨试试这个方法。希望这篇文章能帮到你！
