15

是面试题。

给定一个数字 n，找出在 0...n 范围内有多少个数字为 2 的数字

例如 ，

输入 = 13 输出 = 2（2 和 12）

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

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

4

4 回答 4

27

数一下没有数字 2 的数字。在小于 10 k的数字中，正好有 9 k个。然后剩下的就是处理从 10 k到的数字n，其中

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

您可以通过单独处理第一个数字（必须区分案例 2 和其他案例），然后是前 2 个数字等来做到这一点。

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

2345 - 1458 = 887
于 2012-06-22T13:16:56.330 回答
2

参数 'digit' 是我们要计数的那个，而 arg 'number' 是我们要计数的位置。例如：如果我们要计算 '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;
}
于 2014-02-10T07:14:25.767 回答
0

给定带有数字 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，则在 9+1 位置具有 '2' 的数字的比例是 ，那么在该位置1/(X+1)总共有(T+1)/(X+1)'2'。如果X < 2，则 [0..T] 上的数字在该位置没有“2”。

对于其他数字位置，很容易看出，在每个数字位置，1/10数字都有一个'2'，所以(T+1)/10位置0有' 2' (T+1)/10，位置1有'2'，等等。总共，(T+1) * nines / 10。

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

于 2012-06-23T07:35:07.263 回答
0

这就是我编写初稿（Python 代码）的方式

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

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

就性能而言，它并没有那么糟糕，对于 n=10,000,000，平均迭代大约需要 5.5 秒

于 2013-01-17T00:16:01.460 回答