C++ 实现：从 1 到 n 统计数字 1 出现次数的高效算法

```cpp #include <iostream> using namespace std; int countDigitOne(int n) { int count = 0; long long factor = 1; // 当前位数（个位、十位、百位...） while (n / factor > 0) { int lower = n % factor; // 低位数字 int cur = (n / factor) % 10; // 当前位数字 int higher = n / (factor * 10); // 高位数字 // 根据当前位数字计算1的个数 if (cur == 0) { count += higher * factor; } else if (cur == 1) { count += higher * factor + lower + 1; } else { count += (higher + 1) * factor; } factor *= 10; // 移动到下一位 } return count; } int main() { int n; cin >> n; cout << countDigitOne(n) << endl; return 0; } ``` 算法思路： 1. 逐位统计数字1出现的次数 2. 将数字分为三部分：高位数字、当前位数字、低位数字 3. 根据当前位数字的值分三种情况计算： - 当前位为0：1的个数 = 高位数字 × 当前位数 - 当前位为1：1的个数 = 高位数字 × 当前位数 + 低位数字 + 1 - 当前位≥2：1的个数 = (高位数字 + 1) × 当前位数 示例说明： 输入：12 输出：5 计算过程： - 个位：高位=1，当前位=2，低位=0 → (1+1)×1=2 - 十位：高位=0，当前位=1，低位=2 → 0×10+2+1=3 - 总计：2+3=5 时间复杂度： O(log₁₀ n) 空间复杂度： O(1) ######[AI问答 | 452点数解答 | 2025-12-20 14:49:52]