剑指offer 整数中1出现的次数（python）

剑指offer 整数中1出现的次数（python）

Q: 求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1-13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

粗暴解法：遍历计数时间复杂度： $O(nlogn)$

复杂度为 $O(logn)$ 的解法

推导数学规律(*ω)真滴很难懂

基本思路是将每个数位上中出现1的次数分别计算累加

飒！来吧

首先我们先看一个五位数n，用m来分割高低位；根据设定的整数位置，对n进行分割，分为两部分，高位n//m，低位n%m

此时，分为三种情况：

当i表示百位，且百位对应的数>=2,如n=31456,m=100，则a=314,b=56，
100~199
1100~1199
…
31100~31199
此时百位为1的次数有a//10+1=32（最高两位0~31），每一次都包含m=100个连续的点，即共有(a//10+1)*100个点的百位为1
百位数数字为1时，n = 31156 ,m = 100 , 则a=311, b = 56;
此时，
100~199
…
30100 ~ 30199
31100 ~ 31156
此时，百位上有1的次数变为(a//10)*100+b+1个点
百位数字为0时， n = 31056, m = 100, 则a = 310, b = 56;
100~199
…
30100~30199
一共是 (a//10)*100个符合条件的点

归纳为公式如下：

count = (a + 8) // 10 * m + (a % 10 == 1) * (b + 1)

tricks: 简化代码

这里利用取除数的操作，a + 8 当a >= 2时，自动进1位，满足上述条件

a % 10 == 1判断该位置是否为1，是则返回1，否则返回0。

完整代码如下：

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count, m = 0, 1
        while m <= n:
            count += (n // m + 8) // 10 * m + (n // m % 10 == 1) * (n % m + 1)
            m *= 10
        return count

剑指offer 整数中1出现的次数（python）

剑指offer 整数中1出现的次数（python）

复杂度为O(logn)O(logn)O(logn)的解法

浏览过的版块

复杂度为 $O(logn)$ 的解法