题目描述

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

样例

输入：13
输出：6 
解释：数字 1 出现在以下数字中: 1, 10, 11, 12, 13。

算法

(数位统计) $O(\log n)$

1. $f(i)$ 表示 位数 小于等于 $i$ 的所有正整数中，数字 1 出现的次数。
2. 根据规律，可以得到如下递推公式， $f(i) = f(i - 1) \times 10 + 10^{i - 1}$ ，其中 $f(0) = 0$。
3. 接下来从数字的最高位开始向下统计，主体思路为按位分别统计小于 n 的数字中 1 出现的次数。
4. 如果当前数位等于 1，则该位所贡献的答案数为 $f(i)$ ，并统计更高位的 1 所带来的答案。
5. 如果当前数位大于 1，则该位所贡献的答案数为 $10^i + f(i) \times num[i]$ ，并统计更高位的 1 所带来的答案。
6. 如果当前数位等于 0，则直接跳过即可。

接下来以例子 n = 21301 来解释算法。

1. 预处理 $f(0) = 0, f(1) = 1, f(2) = 20, f(3) = 300, f(4) = 4000$。
2. 从高位开始枚举，当前枚举到最高位为 2，在这里我们需要统计 [00000, 19999] 所具有的 1 的个数，分为两部分计算，一部分是 $10^4$ 代表 [10000, 19999] 中最高位的 1 的个数；另一部分是以 0 和 1 开头时，后四位所具有的 1 的个数，为 $f(4) \times 2$ 。此时还没有更高位的 1 。在接下来的过程，将计算最高位为 2 时，后续 1 的个数。
3. 到第四位 1，在这里需要统计 [20000, 20999] 所具有的 1 的个数，所以直接加上 $f(3)$，此时更高位还没有 1。但此时需要记录这一位的 1。
4. 到第三位 3，在这里需要统计[21000, 21299]所具有的 1 的个数，由于更高位有了 1 ，此时首先需要加上 $3 \times 10^2$ ，代表统计上了第四位的 1。然后分两部分计算，一部分是 $10^2$ 代表 [21100, 21199]所具有的 1 中第三位为 1 的个数；另一部分 $3 \times f(2)$ 是计算 [21000, 21299] 中后两位出现 1 的个数。
5. 到第二位 0，直接跳过。
6. 到最低位 1，此时统计第四位 1 带来的答案，为 $1 \times 10^0$ 。然后由于该位为 1，直接加上 $f(0)$ 。
7. 到此为止还没结束，以上过程只统计了小于 n 的数，最后还需要加上 n 中 1 的个数。

时间复杂度

• 时间复杂度仅与数的长度有关，故为 $O(\log n)$。

空间复杂度

• 空间占用也与数的长度有关，故也为 $O(\log n)$。

注意

• 此题输入的 n 有可能为负数。
• 虽然答案有可能超过 int，但题目并没有要求返回 long long 类型。

C++ 代码

class Solution {
public:
    int countDigitOne(int n) {
        if (n <= 0)
            return 0;

        vector<int> f(10, 0), pow(10, 0);
        f[0] = 0;
        pow[0] = 1;
        for (int i = 1; i <= 9; i++) {
            f[i] = f[i - 1] * 10 + pow[i - 1];
            pow[i] = pow[i - 1] * 10;
        }

        string num = to_string(n);
        reverse(num.begin(), num.end());
        int ans = 0, ones = 0;

        for (int i = num.length() - 1; i >= 0; i--) {
            ans += ones * ((num[i] - '0') * pow[i]);
            if (num[i] == '1') {
                ones++;
                ans += f[i];
            }
            else if (num[i] != '0')
                ans += pow[i] + f[i] * (num[i] - '0');
        }

        return ans + ones;
    }
};