题目描述
输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12,从1到12这些整数中包含“1”的数字有1,10,11和12,其中“1”一共出现了5次。
样例
输入: 12
输出: 5
算法1
(按位数) $O(logn)$
逐位计算1出现在当前位置的次数,累积起来即可得到最终答案。
时间复杂度
一个n位数一共有ln(n) / ln(10)位, 所以渐近复杂度是 O(logn)级别。
参考文献
C++ 代码
// time O(logn), really tricky, count bit by bit
class Solution {
public:
int numberOf1Between1AndN_Solution(int n) {
if (n < 1) return 0;
int count = 0, factor = 1;
while (n / factor != 0) {
int cur_bit = (n / factor) % 10;
int left = n / (factor * 10);
int right = n % factor;
if (cur_bit == 0) {
count += left * factor;
}
else if (cur_bit == 1) {
count += left * factor + right + 1;
}
else {
count += (left + 1) * factor;
}
factor *= 10;
}
return count;
}
};
Python3 代码
# count bit by bit, time O(logn)
class Solution(object):
def numberOf1Between1AndN_Solution(self, n):
"""
:type n: int
:rtype: int
"""
if n < 1: return 0
count = 0
factor = 1
while n // factor:
left = n // (10 * factor)
cur_bit = (n // factor) % 10
right = n % factor
if cur_bit == 0:
count += left * factor
elif cur_bit == 1:
count += left * factor + right + 1
else:
count += (left + 1) * factor
factor *= 10
return count