C++ 给定一个十进制正整数n,写下从1到n的所有整数,然后数一下其中出现的数字“1”的个数。例如当n=2时,写下1,2。这样只出现了1个“1”;当n=12时,写下1,2,3,4,5,6,7,8,9,10,11,12。这样出现了5个“1”。
时间: 2025-01-21 20:28:41 浏览: 76
这是一个经典的算法问题,可以用多种方法来解决。我来介绍一种高效的方法来计算从1到n中数字"1"出现的次数:
```cpp
int countDigitOne(int n) {
long long count = 0; // 使用long long防止溢出
long long i = 1; // 当前位
int current, high, low;
while (i <= n) {
high = n / (i * 10);
current = (n / i) % 10;
low = n % i;
if (current == 0) {
count += high * i;
} else if (current == 1) {
count += high * i + low + 1;
} else {
count += (high + 1) * i;
}
i *= 10;
}
return count;
}
```
这个算法的时间复杂度是O(log n),因为它只需要遍历n的每一位。下面解释一下算法的思路:
1. 我们从个位开始,逐位向高位遍历。
2. 对于每一位,我们计算高位(high)、当前位(current)和低位(low)。
3. 根据当前位的值,我们计算"1"出现的次数:
- 如果当前位是0,那么"1"出现的次数由高位决定:high * i
- 如果当前位是1,那么"1"出现的次数由高位和低位共同决定:high * i + low + 1
- 如果当前位大于1,那么"1"出现的次数由高位决定:(high + 1) * i
4. 将i乘以10,向左移动一位,继续计算。
这个方法巧妙地利用了数位来计算"1"的总数,避免了直接遍历每个数字的低效。
阅读全文
相关推荐


















