题目(从1到n整数中1出现的次数—牛客网)

输入一个整数 n，求 1-n 这 n 个整数的十进制表示中 1 出现的次数。例如，输入12，1-12 这些整数中包含 1 的数字有1、10、11 和 12，1 一共出现了 4 次。

算法思路

最简单的思路就是遍历所有整数，然后对每一个整数再遍历出每一个数位(通过 /、% 运算即可)，最后统计所有整数中含 1 的次数。但是此情况下的时间复杂度达到了 O(nlogn)，能不能降到 O(logn)？。

可以滴！！接下来，提出一个高效算法，它利用了数字的规律，挺不容易想到的。
既然时间复杂度这么低，那么就不可能去单独计算每个整数中 1 出现的次数了，所以就只能研究 1 出现的规律了。
由于我们可以计算出所有整数中 1 出现在每个数位(个位、十位、百位…)的总次数，因此最后 1 到 n 整数中 1 出现的次数=所有整数中含个位且其个位为 1 的总数 + 所有整数中含十位且其十位为 1 的总数+所有整数中含百位且其百位为 1 的总数
+…(项总数取决了 n 含的数位数,共 logn 项)。

下面以百位为例进行分析。我们以百位 i(i=100) 将整数 n 分割为两部分。设a=n/i;b=n%i。

如果 n 的百位上为 0，例如 n=31056，a=310,b=56。那么 1-31056 中百位含 1 的整数必然以 100-199 之间的数字作为后缀(共有100个)。而前缀的范围在 00-30 之间(不包括31的是因为31056中百位不是 1，忽略)，共31个，它等于a/10，因此此情况总的个数就是 a/10*i；
如果 n 的百位上为 1，例如 n=31156，a=311,b=56。那么 1-31156 中百位含 1 的整数必然以 100-199 之间的数字作为后缀(共有100个)。而前缀的范围在 00-30 之间，共31个，但前缀为 31 时，百位含 1 的个数为 (b+1)个，即31100-31156 之间的数，因此此情况总的个数就是 a/10 *i+(b+1)；
如果 n 的百位上数字大于等于2 ，例如 n=31256，a=312,b=56。那么 1-31256 中百位含 1 的整数必然以 100-199 之间的数字作为后缀(共有100个)。而前缀的范围在 00-31 之间，共32个,因此此情况总的个数就是 (a/10 +1) *i。

最后，将三种情况进行整合，得 (a+8)/10 *i，当百位大于等于 2 时，a多加了8就会进1，此时等价于情况 3 中的式子。最后利用 a%10判断整数 n 的百位是否为1，若为 1 ，则总次数还要多加上(b+1)。

算法实现

复杂度

由于算法只遍历了整数 n 的每个数位(共 logn 位)，所以算法的时间复杂度仅为 O(logn)。

参考

[1] <<剑指offer2>>
[2] 牛客网