该题是剑指 Offer 中一道考验分析数字规律的题,在 LeetCode 上看到一种十分巧妙的方法,为此在这里记录一下,以便日后复习。

题目描述

求出任意非负整数区间中 1 出现的次数,即在 1 到 n 中,1 所出现的次数。

分析

方法一

最能想到的方法就是累加 1 到 n 中每个整数 1 出现的次数,如果当前数字大于 10,则可以对 10 求余的方式判断该数的个位数字是不是 1,不断的累加直到输出最后结果。

当然这种方式的时间复杂度很高,为 O(nlogn),通常也不是面试官想要的答案,他会问你有没有更好的方法?

方法二

我们可以利用 1101001000……这样的数来作为输入数字 n 划分的依据,例如输入的数字是 21396,我们可以考虑个位、十位、百位、千位……的划分情况,这里以 百位 为例,由于百位上的数字范围是从 09,所以可以将其分为 百位数字大于等于 2百位数字等于 1 以及 百位数字等于 0 三种情况,下面分别讨论:

情况一

对于 百位数字大于等于 2 的情况,如数字 21396,则有以下情况:

小技巧:对于 x % y 操作,运算结果会在 0 ~ (y - 1) 之间。


例如 123 % 5 = 4,其结果一定在 0 ~ 4 之间,不管是 123 还是像 1231241 这样多大的数,经过取余运算,其结果都会在 0 ~ 4 之间的。

序号 对应的情况
1 100 ~ 199
2 1100 ~ 1199
3 2100 ~ 2199
4 3100 ~ 3199
5 4100 ~ 4199
6 5100 ~ 5199
7 6100 ~ 6199
8 7100 ~ 7199
9 8100 ~ 8199
20 19100 ~ 19199
21 20100 ~ 20199
22 21100 ~ 21199
剩余情况则不满足

为了便于计算,先得到 a = 21396 / 100 = 213b = 21396 % 100 = 96

所以,对于 百位数字大于等于 2 的情况,共有 (a / 10 + 1) * 100 = 2200 个数字是含有 1 的。也就是说,在 (213 / 10 + 1) = 22 的情况下,每种情况有 0 ~ 99 个数。

情况二

对于 百位数字等于 1 的情况,如数字 21196,则有以下情况:

序号 对应的情况
1 100 ~ 199
2 1100 ~ 1199
3 2100 ~ 2199
4 3100 ~ 3199
5 4100 ~ 4199
6 5100 ~ 5199
7 6100 ~ 6199
8 7100 ~ 7199
9 8100 ~ 8199
20 19100 ~ 19199
21 20100 ~ 20199
22 21100 ~ 21196

对于这种情况,共有 (a / 10) * 100 + (b + 1) = 2197 个数字是含有 1 的。注意序号 22 对应的就是 (b + 1) 这部分,我们将其单独计算,即 (96 + 1) = 97

情况三

对于 百位数字等于 0 的情况,如数字 21096,则有以下情况:

序号 对应的情况
1 100 ~ 199
2 1100 ~ 1199
3 2100 ~ 2199
4 3100 ~ 3199
5 4100 ~ 4199
6 5100 ~ 5199
7 6100 ~ 6199
8 7100 ~ 7199
9 8100 ~ 8199
20 19100 ~ 19199
21 20100 ~ 20199
22(该情况不满足) 21100 ~ 21196

注意序号 22,该情况大于了给定的数字 21096,所以不考虑,将其划掉。

则这种情况下共有 (a / 10) * 100 = 2100 个数字是含有 1 的。

情况汇总

可以看到,对于 百位数字大于等于 2百位数字等于 0 的情况是可以结合起来的,也就是 (a + 8) / 10 * 100;而对于 百位数字等于 1 的情况,可以用 (a + 8) / 10 * 100 + (b + 1) 表示。

之所以补上 8,是因为当百位为 0 时,则有 a / 10 == (a + 8) / 10;当百位大于等于 2 时,补 8 会产生进位,等价于 (a / 10 + 1)

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int res = 0;
        for (int m = 1; m <= n; m *= 10) {
            int a = n / m, b = n % m;
            res += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
        }
        return res;
    }
}

参考

https://leetcode.com/problems/number-of-digit-one/discuss/64381/4+-lines-O(log-n)-C++JavaPython
https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6?f=discussion