You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

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

. 3 min read

【数学】

给定一个在 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% 的用户

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)$