43.整数中1出现的次数.md

31.整数中1出现的次数

题目描述

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

输入

13

输出

6

思路 & 解答

这道题如果使用暴力破解，肯定是会超时的，所以我们需要看看这里面有没有啥规律。（这规律并非我自己发现的，从别人的答案中得知，直呼牛逼）

假设现在有一个是为 num,num 是位数一共为x，n1 个位，n2 表示十位，nx 表示最高位，那么num就可以表示为：nxnx-1nx-2...n3n2n1。 比如3504，最高位是3，百位是5，十位是0，个位是4，拿十位来说，比十位更高的位上的数是3，5，比十位更低的位数上的数是4。

当前位是0

假设当前位上的数是0，譬如3504，那么35是高位，4是低位，当前位是十位，也就是10，1出现的可能性是哪些呢？

从001X到341X

猜想一下，前面的千位和百位的组合是不是可以从00到34，有人说为什么不到35，351X明显超出范围了！！！ 那后面的X是不是可以随意的0到9呢？那肯定是啊，所以前面00到34一共35个数，0到9一共10个数，这个10也就是因为当前的1在十位上。 所以当前位是0的时候，该位出现1的数字个数是：

$$ 高位*当前位数 = 35 *10 =350 $$

当前位是1

假设我们现在计算的是3514，当前位是1，高位是35，低位是4。除了前面说的高位从00到34，低位可以从0到9，之外。仔细观察！！！

351X

如果高位是35的时候，低位是不是可以从0-4，一共五个数。最大的数是3514，所以当前位是1的时候，当前位数出现1的个数是：

$$ 高位当前位数+低位+1 = 3510+4+1 = 355 $$

当前位>1

假设我们现在计算的是3524，当前位是2，高位是35，低位是4。我们发现，当前位是1的时候，高位可以从0到35，而低位是可以从0到9，最小是0010，最大是3519。 因此当前位大于2的时候，所有数字中出现1的个数是： $$ （高位+1）*当前位数 = （1+35）*10 = 360 $$

每一位上出现1的次数都依照上面的算法，就可以得出出现1的所有次数。代码如下：

    public static int NumberOf1Between1AndN_Solution(int n) {
        int sum = 0;
        int level = 1;
        int high = n / 10;
        int low = 0;
        int cur = n % 10;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                sum = sum + high * level;
            } else if (cur == 1) {
                sum = sum + high * level + low + 1;
            } else {
                sum = sum + (high + 1) * level;
            }
            low = cur * level + low;
            level = level * 10;
            cur = high % 10;
            high = high / 10;
        }
        return sum;
    }

C++ 代码实现如下：

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int sum = 0;
        int level = 1;
        int high = n / 10;
        int low = 0;
        int cur = n % 10;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                sum = sum + high * level;
            } else if (cur == 1) {
                sum = sum + high * level + low + 1;
            } else {
                sum = sum + (high + 1) * level;
            }
            low = cur * level + low;
            level = level * 10;
            cur = high % 10;
            high = high / 10;
        }
        return sum;
    }
};

不得不说，找到这个规律的人真的超级牛逼！！！

• 时间复杂度 O(log n) ： 循环数字 n 的位数，相当于使用了 log(n)，时间复杂度为 O(log n)
• 空间复杂度 O(1)：