范围内的数字计数 - Digit Count in Range

【数学】

Problem Link

给定一个在 0 到 9 之间的整数 d，和两个正整数 low 和 high 分别作为上下界。返回 d 在 low 和 high 之间的整数中出现的次数，包括边界 low 和 high。

Example:

示例 1：

输入：d = 1, low = 1, high = 13
输出：6
解释： 
数字 d=1 在 1,10,11,12,13 中出现 6 次。注意 d=1 在数字 11 中出现两次。

示例 2：

输入：d = 3, low = 100, high = 250
输出：35
解释：
数字 d=3 在 103,113,123,130,131,...,238,239,243 出现 35 次。

提示：

0 <= d <= 9
1 <= low <= high <= 2×10^8

Analysis

给定范围计算显然不是简单的数学模型

划归到计算 [0, N] 中 d 出现的次数会容易很多，找规律即可

接下来的难点在于 0 不会出现在最高位，需要进行单独的判断。

利用数学公式可以直接计算出最终的结果，该方法是依次求出数字 X 在个位、十位、百位等等出现的次数，再相加得到最终结果。这里的 $X \in [1,9]$，因为 $X=0$ 不符合下列规律，需要单独计算。

首先要知道以下的规律，可由数学归纳法证明：

N ∈ $[1, 10]$，在它们的个位数中，任意的 X 都出现了 1 次。
N ∈ $[1, 100]$，在它们的十位数中，任意的 X 都出现了 10 次。
N ∈ $[1, 1000]$，在它们的千位数中，任意的 X 都出现了 100 次。
...
N ∈ $[1, 10^i]$，在它们的左数第二位（右数第 $i$ 位）中，任意的 X 都出现了 $10^{i-1}$ 次。

伪代码描述如下：

当计算右数第 $i$ 位包含的 X 的个数时：

当 X != 0 时：

取第 $i$ 位左边（高位）的数字，乘以 $10^{i-1}$，得到基础值 $a$。

取第 $i$ 位数字，计算修正值：

如果大于 X，则结果为 $a + 10^{i-1}$。

如果小于 X，则结果为 $a$。

如果等 X，则取第 $i$ 位右边（低位）数字，设为 $b$，最后结果为 $a + b + 1$。

当 X = 0 时，由于最高位中永远是不会包含 0 的，因此：

从个位累加到左起第二位就要结束
第 $i$ 位的基础值是高位数字乘以 $10^{i-1}-1$

时间复杂度： $O({\log _{10}}n)$

Solution 【数学】

执行用时 : 1 ms, 在Digit Count in Range的Java提交中击败了100.00% 的用户

内存消耗 : 33.6 MB, 在Digit Count in Range的Java提交中击败了100.00% 的用户

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
    public int digitsCount(int d, int low, int high) {
        return count(high, d) - count(low - 1, d);
    }
    
    /* 计算数字 d 在 1-n 中出现的次数。 */
    public int count(int n, int d) {
        int cnt = 0, k;
        for (int i = 1;(k = n / i) != 0;i *= 10) {
            // 高位的数字。
            int high = k / 10;
            if (d == 0) {
                if (high != 0) {
                    high--;
                } else {
                    break;
                }
            }
            cnt += high * i;
            // 当前位的数字。
            int cur = k % 10;
            if (cur > d) {
                cnt += i;
            } else if (cur == d) {
                // n - k * i 为低位的数字。
                cnt += n - k * i + 1;
            }
        }
        return cnt;
    }
    
}

复杂度分析

时间：$O(log_{10}N)$

空间：$O(1)$