「Swift 实战」如何高效统计 1 到 n 之间出现的 “1“？

摘要

数字 “1” 在我们的生活中无处不在，但如果让你数一数 0 到 n 之间出现了多少次 “1”，你会怎么做？是一个个遍历，还是有更聪明的方法？这篇文章会带你用 Swift 解决这个问题，而且是 超高效 的方法！

问题描述

想象一下，你在做一些数据分析，比如：

• 想统计车牌号码里 “1” 出现的次数
• 想分析某个网站用户 ID 里 “1” 的分布情况
• 研究彩票号码，看 “1” 这个数字的频率

如果 n 很小，我们还能手动数一数，但 n 一旦变大，比如 1,000,000,000，手动统计就完全不现实了。那该怎么办呢？

常见思路

最容易想到的方法是 暴力遍历：

var count = 0
for i in 0...n {
    count += String(i).filter { $0 == "1" }.count
}

看起来没毛病，但如果 n = 1,000,000,000，代码可能要跑到明天早上。效率太低，完全不行。

有没有更快的方法？当然有！

高效解法：逐位分析

我们可以不去 一个个数 “1” 的次数，而是分析 每一位 里 “1” 的贡献，快速得出最终答案。

Swift 代码

func countDigitOne(_ n: Int) -> Int {
    var count = 0
    var factor = 1
    var currentN = n

    while 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 *= 10
        currentN /= 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)，比暴力遍历快得多。

示例测试及结果

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” 出现的概率

如果你以后遇到类似的 大数据统计问题，不妨试试这个方法。希望这篇文章能帮到你！