【数学】
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% 的用户
|
|
复杂度分析
时间:$O(log_{10}N)$
空间:$O(1)$