统计1到n中数字1出现次数的C++高效算法及实现详解

这道题是典型的**数字统计问题**，要求统计从 1 到 n 的所有整数中，数字 1 出现的总次数。 --- ## 🧠 解题思路分析 有两种常见解法： ### 1. 暴力枚举法（简单但效率低） - 遍历从 1 到 n 的每个整数，对每个整数逐位判断是否为 1。 - **时间复杂度**：O(n × log₁₀n)，当 n 很大时（如 10⁹）会超时。 - 适合 n 较小的情况（如 n ≤ 10⁶）。 ### 2. 数学规律法（高效） - 按位统计每一位上 1 出现的次数，利用数位规律直接计算。 - **时间复杂度**：O(log₁₀n)，可处理极大范围的 n。 --- ## 🚀 高效解法（按位统计法） ### 核心规律 对于第 `i` 位（从右往左，个位为第 0 位），统计该位上数字 1 出现的次数，只需考虑三个值： - `high`：当前位左边的数字 - `cur`：当前位的数字 - `low`：当前位右边的数字 **计算规则**（设当前位的权值为 `factor = 10^i`）： 1. 如果 `cur == 0`：该位 1 出现次数 = `high × factor` 2. 如果 `cur == 1`：该位 1 出现次数 = `high × factor + low + 1` 3. 如果 `cur > 1`：该位 1 出现次数 = `(high + 1) × factor` --- ## 💻 C++ 代码实现 ```cpp #include <iostream> using namespace std; long long countDigitOne(long long n) { long long count = 0; long long factor = 1; // 位权，从个位开始 while (n / factor != 0) { long long high = n / (factor * 10); // 当前位左边的数字 long long cur = (n / factor) % 10; // 当前位的数字 long long low = n % factor; // 当前位右边的数字 if (cur == 0) { count += high * factor; } else if (cur == 1) { count += high * factor + low + 1; } else { count += (high + 1) * factor; } factor *= 10; // 下一位 } return count; } int main() { long long n; cin >> n; cout << countDigitOne(n) << endl; return 0; } ``` --- ## 📊 算法复杂度分析 | 指标 | 复杂度 | |------|--------| | 时间复杂度 | O(log₁₀ n) | | 空间复杂度 | O(1) | --- ## 🧪 测试样例验证 | 输入 n | 预期输出 | 说明 | |--------|----------|------| | 2 | 1 | 只有数字 1 包含一个 1 | | 12 | 5 | 1, 10, 11（两个）, 12 共 5 个 1 | | 100 | 21 | 1~9:1, 10~19:11, 21~91:8, 100:1，合计 21 | --- ## ⚠️ 开发建议与注意事项 1. **数据范围**：n 可能很大（如 10⁹ 甚至更大），务必使用 `long long` 类型，防止溢出。 2. **边界条件**：当 n = 0 时，直接输出 0（题目保证 n 为正整数，但代码仍应健壮）。 3. **循环终止条件**：使用 `while (n / factor != 0)` 确保处理到最高位。 4. **暴力法适用场景**：如果 n ≤ 10⁶，暴力枚举更简单直观；但题目未限定范围，推荐使用高效解法。 --- ## 📚 扩展学习 - 类似题目：统计数字 2~9 出现的次数，原理完全相同，只需将代码中的 `1` 替换为目标数字即可。 - 进阶思考：如果要求统计所有数字（0~9）的分布，可以复用此逻辑并对每位循环统计。 ######[AI写代码神器 | 989点数解答 | 2026-08-16 17:49:02]