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

【数学】

Problem Link

给定一个在 09 之间的整数 d,和两个正整数 lowhigh 分别作为上下界。返回 dlowhigh 之间的整数中出现的次数,包括边界 lowhigh

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 次。

提示:

  1. 0 <= d <= 9
  2. 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
33
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)$

updatedupdated2021-03-052021-03-05