https://blog.csdn.net/kkdd2013/article/details/51882774
计算数字k在0到n中的出现的次数,k可能是0~9的一个值
例如n=12,在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]中,我们发现1出现了5次 (1, 10, 11, 12)
思路一:我们可以用最简单的办法先尝试一下,遍历1到n中间的每个整数,对每个整数从低位到高位依次检查,如果有k出现则计数器自加。
思路一最大的问题就是效率,当n非常大时,就需要很长的运行时间。想要提高效率,就要避开暴力法,从数字中找出规律。
思路二:来自《编程之美》
假设有一个5位数N=ABCDE,我们现在来考虑百位上出现2的次数,即:从0到ABCDE的数中,有多少个数的百位上是2。分析完它,就可以用同样的方法去计算个位,十位,千位,万位等各个位上出现2的次数。
第一种情况:当百位上的数C小于2时:
1)当百位c为0时,比如说12013,0到12013中哪些数的百位会出现2?我们从小的数起, 200~299, 1200~1299, 2200~2299, … , 11200~11299, 也就是固定低3位为200~299,然后高位依次从0到11,共12个。再往下12200~12299 已经大于12013,因此不再往下。所以,当百位为0时,百位出现2的次数只由更高位决定,等于更高位数字(12)x当前位数(100)=1200个。
2)当百位C为1时,比如说12113。分析同上,并且和上面的情况一模一样。最大也只能到11200~11299,所以百位出现2的次数也是1200个。
上面两步综合起来,可以得到以下结论:
—>当某一位的数字小于2时,那么该位出现2的次数为:更高位数字x当前位数
第二种情况:当百位上的数C等于2时:
当百位C为2时,比如说12213。那么,我们还是有200~299, 1200~1299, 2200~2299, … , 11200~11299这1200个数,他们的百位为2。但同时,还有一部分12200~12213,共14个(低位数字+1)。所以,当百位数字为2时,百位出现2的次数既受高位影响也受低位影响,结论如下:
—>当某一位的数字等于2时,那么该位出现2的次数为:更高位数字x当前位数+低位数字+1
第三种情况:当百位上的数C大于2时:
当百位C大于2时,比如说12313,那么固定低3位为200~299,高位依次可以从0到12,这一次就把12200~12299也包含了,同时也没低位什么事情。因此出现2的次数是: (更高位数字+1)x当前位数。结论如下:
—>当某一位的数字大于2时,那么该位出现2的次数为:(更高位数字+1)x当前位数
通过上述分析,我们可以得到以下规律:
当某一位的数字小于i时,那么该位出现i的次数为:更高位数字x当前位数
当某一位的数字等于i时,那么该位出现i的次数为:更高位数字x当前位数+低位数字+1
当某一位的数字大于i时,那么该位出现i的次数为:(更高位数字+1)x当前位数
int digitCounts2(int n, int k)
{
int result = 0;
int base = 1;
while (n/base > 0)
{
int cur = (n/base)%10;
int low = n - (n/base) * base;
int high = n/(base * 10);
if (cur == k)
{
result += high * base + low + 1;
} elseif (cur <k)
{
result += high * base;
} else
{
result += (high + 1) * base;
}
base *= 10;
}
return result;
}
https://blog.csdn.net/zhaoxiangyu1/article/details/47208107
http://www.cnblogs.com/cyjb/p/digitOccurrenceInRegion.html
计算数字k在0到n中的出现的次数,k可能是0~9的一个值
例如n=12,在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]中,我们发现1出现了5次 (1, 10, 11, 12)
思路一:我们可以用最简单的办法先尝试一下,遍历1到n中间的每个整数,对每个整数从低位到高位依次检查,如果有k出现则计数器自加。
思路一最大的问题就是效率,当n非常大时,就需要很长的运行时间。想要提高效率,就要避开暴力法,从数字中找出规律。
思路二:来自《编程之美》
假设有一个5位数N=ABCDE,我们现在来考虑百位上出现2的次数,即:从0到ABCDE的数中,有多少个数的百位上是2。分析完它,就可以用同样的方法去计算个位,十位,千位,万位等各个位上出现2的次数。
第一种情况:当百位上的数C小于2时:
1)当百位c为0时,比如说12013,0到12013中哪些数的百位会出现2?我们从小的数起, 200~299, 1200~1299, 2200~2299, … , 11200~11299, 也就是固定低3位为200~299,然后高位依次从0到11,共12个。再往下12200~12299 已经大于12013,因此不再往下。所以,当百位为0时,百位出现2的次数只由更高位决定,等于更高位数字(12)x当前位数(100)=1200个。
2)当百位C为1时,比如说12113。分析同上,并且和上面的情况一模一样。最大也只能到11200~11299,所以百位出现2的次数也是1200个。
上面两步综合起来,可以得到以下结论:
—>当某一位的数字小于2时,那么该位出现2的次数为:更高位数字x当前位数
第二种情况:当百位上的数C等于2时:
当百位C为2时,比如说12213。那么,我们还是有200~299, 1200~1299, 2200~2299, … , 11200~11299这1200个数,他们的百位为2。但同时,还有一部分12200~12213,共14个(低位数字+1)。所以,当百位数字为2时,百位出现2的次数既受高位影响也受低位影响,结论如下:
—>当某一位的数字等于2时,那么该位出现2的次数为:更高位数字x当前位数+低位数字+1
第三种情况:当百位上的数C大于2时:
当百位C大于2时,比如说12313,那么固定低3位为200~299,高位依次可以从0到12,这一次就把12200~12299也包含了,同时也没低位什么事情。因此出现2的次数是: (更高位数字+1)x当前位数。结论如下:
—>当某一位的数字大于2时,那么该位出现2的次数为:(更高位数字+1)x当前位数
通过上述分析,我们可以得到以下规律:
当某一位的数字小于i时,那么该位出现i的次数为:更高位数字x当前位数
当某一位的数字等于i时,那么该位出现i的次数为:更高位数字x当前位数+低位数字+1
当某一位的数字大于i时,那么该位出现i的次数为:(更高位数字+1)x当前位数
int digitCounts2(int n, int k)
{
int result = 0;
int base = 1;
while (n/base > 0)
{
int cur = (n/base)%10;
int low = n - (n/base) * base;
int high = n/(base * 10);
if (cur == k)
{
result += high * base + low + 1;
} elseif (cur <k)
{
result += high * base;
} else
{
result += (high + 1) * base;
}
base *= 10;
}
return result;
}
https://blog.csdn.net/zhaoxiangyu1/article/details/47208107
public static int digitCounts(int k, int n) {
int result = 0;
int base = 1; //位, 个位/十位/百位
if (k == 0 && n == 0) {
return 1;
}
while (n / base > 0) {
int cur = (n / base) % 10;
int low = n - (n/base) * base;
int hight = n / (base * 10);
if (k == 0 && cur > k){
if (hight != 0) {
result += hight + 1;
} else {
result += hight;
}
} else if (cur == k){
result += hight * base + low + 1;
} else if (cur < k ){
result += hight * base;
} else {
result += (hight + 1) * base;
}
base *= 10;
}
return result;
}
http://www.cnblogs.com/cyjb/p/digitOccurrenceInRegion.html
最简单的办法就是依次遍历 1 至 n,再分别求每个数字中 X 出现的次数,代码如下所示:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <stdio.h> // 计算数字 X 在 n 中出现的次数。 int countOne( int n, int x) { int cnt = 0; for (;n > 0;n /= 10) { if (n % 10 == x) { cnt++; } } return cnt; } // 计算数字 X 在 1-n 中出现的次数。 int count( int n, int x) { int cnt = 0; for ( int i = 1;i <= n;i++) { cnt += countOne(i, x); } return cnt; } int main() { printf ( "%d\n" , count(237, 1)); } |
这个方法的缺点是时间复杂度太高,countOne 方法的时间复杂度是 ,count 方法的时间复杂度是 。
一个更好的办法是利用数学公式直接计算出最终的结果,该方法是依次求出数字 X 在个位、十位、百位等等出现的次数,再相加得到最终结果。这里的 ,因为 不符合下列规律,需要单独计算。
首先要知道以下的规律:
- 从 1 至 10,在它们的个位数中,任意的 X 都出现了 1 次。
- 从 1 至 100,在它们的十位数中,任意的 X 都出现了 10 次。
- 从 1 至 1000,在它们的千位数中,任意的 X 都出现了 100 次。
依此类推,从 1 至 ,在它们的左数第二位(右数第 位)中,任意的 X 都出现了 次。
这个规律很容易验证,这里不再多做说明。
接下来以 为例来解释如何得到数学公式。从 1 至 2593 中,数字 5 总计出现了 813 次,其中有 259 次出现在个位,260 次出现在十位,294 次出现在百位,0 次出现在千位。
现在依次分析这些数据,首先是个位。从 1 至 2590 中,包含了 259 个 10,因此任意的 X 都出现了 259 次。最后剩余的三个数 2591, 2592 和 2593,因为它们最大的个位数字 3 < X,因此不会包含任何 5。
然后是十位。从 1 至 2500 中,包含了 25 个 100,因此任意的 X 都出现了 次。剩下的数字是从 2501 至 2593,它们最大的十位数字 9 > X,因此会包含全部 10 个 5。最后总计 250 + 10 = 260。
接下来是百位。从 1 至 2000 中,包含了 2 个 1000,因此任意的 X 都出现了 次。剩下的数字是从 2001 至 2593,它们最大的百位数字 5 == X,这时情况就略微复杂,它们的百位肯定是包含 5 的,但不会包含全部 100 个。如果把百位是 5 的数字列出来,是从 2500 至 2593,数字的个数与百位和十位数字相关,是 93+1 = 94。最后总计 200 + 94 = 294。
最后是千位。现在已经没有更高位,因此直接看最大的千位数字 2 < X,所以不会包含任何 5。到此为止,已经计算出全部数字 5 的出现次数。
总结一下以上的算法,可以看到,当计算右数第 位包含的 X 的个数时:
- 取第 位左边(高位)的数字,乘以 ,得到基础值 。
- 取第 位数字,计算修正值:
- 如果大于 X,则结果为 。
- 如果小于 X,则结果为 。
- 如果等 X,则取第 位右边(低位)数字,设为 ,最后结果为 。
相应的代码非常简单,效率也非常高,时间复杂度只有 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| // 计算数字 X 在 1-n 中出现的次数。 int count( int n, int x) { int cnt = 0, k; for ( int i = 1;k = n / i;i *= 10) { // k / 10 为高位的数字。 cnt += (k / 10) * i; // 当前位的数字。 int cur = k % 10; if (cur > x) { cnt += i; } else if (cur == x) { // n - k * i 为低位的数字。 cnt += n - k * i + 1; } } return cnt; } |
当 X = 0 时,规律与上面给出的规律不同,需要另行考虑。
最主要的区别是,最高位中永远是不会包含 0 的,因此,从个位累加到左起第二位就要结束,需要将上面代码中 for 循环的判断条件改为 k / 10 != 0。
其次是,第 位的基础值不是高位数字乘以 ,而是乘以 。以 1 至 102 为例,千位中实际包含 3 个 0,但这三个 0 是来自于个位 2 计算得到的修正值,而非来自于基础值。千位的基础值是 0,因为不存在数字 01, 02, 03, ..., 09,即数字前是没有前导 0 的。解决办法就是将上面代码中第 6 行改为 cnt += (k / 10 - 1) * i。
经过综合与化简,得到了以下代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| // 计算数字 0 在 1-n 中出现的次数。 int countZero( int n) { int cnt = 0, k; // k / 10 为高位的数字。 for ( int i = 1;(k = n / i) / 10;i *= 10) { cnt += (k / 10) * i; // k % 10 为当前位的数字。 if (k % 10 == 0) { // n - k * i 为低位的数字。 cnt += n - k * i + 1 - i; } } return cnt; } |
主要是将一些步骤进行了合并,令代码比较简练。
将上面两段代码进行合并,可以得到以下代码,对 X 从 0 到 9 都有效:
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
| // 计算数字 X 在 1-n 中出现的次数。 int count( int n, int x) { int cnt = 0, k; for ( int i = 1;k = n / i;i *= 10) { // 高位的数字。 int high = k / 10; if (x == 0) { if (high) { high--; } else { break ; } } cnt += high * i; // 当前位的数字。 int cur = k % 10; if (cur > x) { cnt += i; } else if (cur == x) { // n - k * i 为低位的数字。 cnt += n - k * i + 1; } } return cnt; } |