请统计某个给定范围[L, R]的所有整数中,数字2出现的次数。 比如给定范围[2, 22],数字2在数2中出现了1次,在数12中出现1次,在数20中出现1次,在数21中出现1次,在数22中出现2次,所以数字2在该范围内一共出现了6次。
时间: 2024-05-31 18:07:49 浏览: 65
# 在一个数组中除了一个数字只出现1次外,其他均出现2次,求这个数字
算法一:
对于每个数字,将其转化为字符串,再统计字符串中2的个数。
时间复杂度:O((R-L+1)log(R))
算法二:
按位统计数字2的个数。
对于[100, 299]这个范围,我们先统计百位上数字2的个数。百位上每出现一次2,就会有100个数的百位为2。百位上数字2的个数为:
(299 / 100 + 1) * 100 / 10 = 30
对于十位和个位同样的方法,最后把三者加起来即可。
时间复杂度:O(log(R))
阅读全文