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

题目描述

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

分析

方法一

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

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

方法二

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

情况一

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

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

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

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

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

情况二

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

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

情况三

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

注意序号 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