题 给定一个数字n,找出0 ... n范围内有数字2的数字


这是一个面试问题。

给定一个数字n,找出0 ... n范围内有数字2的数字

例如 ,

输入= 13输出= 2(2和12)

我给出了通常的O(n ^ 2)解决方案,但有更好的方法。

是否有任何“技巧”公式可以帮助我立即得到答案


14
2018-06-22 13:12


起源


O(N²)?如果你的意思是,生成数字并检查数字,即O(n lg n),因为每个数字n由O(lg n)数字表示。 - Fred Foo
这是一个排列问题.. - Anil Kumar Arya


答案:


计算那些数字  有数字2.小于10的数字ķ,正好有9个ķ 他们然后它仍然是从10处理数字ķ 至 n,哪里

10^k <= n < 10^(k+1)

您可以通过单独处理第一个数字(案例2和其他必须区分),然后前两个数字等来做。

例如,对于 n = 2345,我们发现有 9^3 = 729 没有数字2低于1000的数字。在1000到1999的范围内再有729个这样的数字。然后在2000到2345的范围内,没有,总共1458,因此包含数字2的数字是

2345 - 1458 = 887

26
2018-06-22 13:16



你能解释一下你是如何得到9 ^ k的数字的,我对组合数据并不是很好。 - nikhil
如果您使用前导零写数字,则数字0到 10^k - 1 正是你可以准确写出的数字 k 数字。对于每个数字,有9(== 10 - 1)可能的选择(0,1,3,4,5,6,7,8,9)。选择是独立的,因此选择的总数是每个数字的选择数量的乘积, 9*9*...*9 = 9^k。如果你的数字不包含数字2和数字5,那么它就是 8^k (8 = 10 - 2)。同样的原则适用于其他基础中数字的表示。但是,由于数字实际上没有前导零,因此... - Daniel Fischer
...,禁止数字0略有不同。然后你不能添加前导零来获得相同长度的所有数字,以及下面的数字计数 10^k 没有数字0的是 9^1 + 9^2 + 9^3 + ... + 9^k = 9 * (9^k - 1)/8。如果你禁止0和 d 其他数字,离开 e = 9-d 符合条件的数字,你得到 e^1 + e^2 + ... + e^k = e * (e^k - 1)/(e-1)。 (将9替换为 base-1 适用于10.)以外的基地 - Daniel Fischer
非常感谢您的好解释。 - nikhil


参数'digit'是我们想要计算的数字,arg'数字'是我们想要计算的地方。例如:如果我们想要计算'1'的出现次数,从0到12,则使用digit = 1和number = 12调用该函数,它将返回出现次数“1”。

int countOccurrences(int digit, int number)
{
    int counter = 0;
    for(int i=1; i<number; i++)
    {
        int j = i;
        while(j > 0)
        {
            if(j%10 == digit)
                counter++;
            j /= 10;
        }
    }
    return counter;
}

1
2018-02-10 07:14



用一些解释解释一下.. - Sankarann
countOccurrences(1,20)= 3; //错误 - SMUsamaShah
你试过这个方法吗?它在countOccurrences(1,20)上返回12,而不是3。 - undeadlock
这计算两个,而不是有多少数字有两个。例如。当它达到22时,它增加两次,而不是一次,这是错误的。 - w0mbat


给定数字ABCDEF,您可以计算范围中的'2'的数量 [0,F], [0,E9], [0,D99], [0,C999], [0,B9999] 和 [0,A99999] 并添加它们。

然后是范围 [0, X9999...999],最高的数字 T = X9999...999 可写成 (X+1) * 10<sup>nines</sup> -1

该范围内的'2'的数量是:

((X >= 2 ? 1/(X + 1)) : 0) + nines/10 ) * (T + 1);

那就是:如果 X >= 2,在nines + 1位置具有'2'的数字的分数是 1/(X+1),总共有 (T+1)/(X+1) '2'在那个位置。如果 X < 2,那么[0..T]上的数字在该位置没有'2'。

对于其他数字位置,很容易看到在每个数字位置, 1/10 数字有一个'2',所以有 (T+1)/10 '2位于0位置, (T+1)/10 '2位于第1位,等等。总的来说, (T+1) * nines / 10

该解决方案的复杂性为O(logN)。


0
2018-06-23 07:35





这是我如何编写我的初稿(Python代码)

def count2(n) :
    return [p for p in range(n+1) if '2' in str(p)]

这将返回一个包含所包含号码的列表。

在性能方面它并没有那么糟糕,因为n = 10,000,000,平均迭代需要大约5.5秒


0
2018-01-17 00:16