📃 题目描述

题目链接：剑指 Offer 43. 1～n 整数中 1 出现的次数 (opens new window)

注意这里是十进制，而不是二进制！

🔔 解题思路

直接看 LeetCode 官方题解 (opens new window) 就行

我们可以从小到大枚举 k。如果 n≥10^k，说明 n 包含 10^k 对应的数位，我们就可以计算这一数位 1 的个数并累加，否则退出枚举（比如 n>=10^2(100)，说明 n 是有百位的，我们就可以计算从 1 ~ n 百位上 1 的个数）。

class Solution {
    public int countDigitOne(int n) {
        int count = 0;
        
		// k = 0 表示个位，k = 10 表示十位......
        for (int k = 0; n >= Math.pow(10, k); k ++) {
            long mulk = (long) Math.pow(10, k);
            count += (n / (mulk * 10)) * mulk;

            // 剩下数的最高位有多少个 1
            long rest = n % (mulk * 10);
            // if (rest < mulk) {
            //     count += 0;
            // }
            if (rest >= mulk && rest < mulk + mulk) {
                count += rest - mulk + 1;
            }
            else if (rest >= mulk + mulk) {
                count += mulk;
            }
        }

        return count;
    }
}

💥 复杂度分析

• 空间复杂度：O(1)
• 时间复杂度：O(LogN)