计算1到N中包含数字1的个数
今天看到一道有趣的算法题，题目如下：N为正整数，计算从1到N的所有整数中包含数字1的个数。比如，N=10，从1，2...10，包含有2个数字1。
相信很多人都能立刻得出以下的解法：
for(n:N)
{
判断n包含1的个数；
累加计数器；
}
这是最直接的解法，但遗憾的是，时间复杂程度为O(N*logN)。因为还需要循环判断当前的n的各位数，该判断的时间复杂程度为O(logN)。
接下来就应该思考效率更高的解法了。说实话，这道题让我想起另外一道简单的算法题：
N为正整数，计算从1到N的整数和。
很多人都采用了循环求解。然后利用初等数学知识就知道S=N*(N+1)/2，所以用O(1)的时间就可以处理。
再回到本道题目，同理应该去寻找到结果R与N之间的映射关系。
分析如下：
假设N表示为aa...a，其中a(1<=i<=n)表示N的各位数上的数字。
c表示从整数1到整数a...a中包含数字1的个数。
x表示从整数1到10^i - 1中包含数字1的个数，例如，x表示从1到9的个数，结果为1；x表示从1到99的个数，结果为20；
当a=0时，c = 0;
当a=1时，c = 1;
当a>1时，c = 1;
当a=1时，c = a +1+ c + x;
当a>1时，c = a*x+c+10;
当a=1时，c = a*a +1+ c + x;
当a>1时，c = a*x+c+10^2;
......
以此类推
当a=1时，c = a*...*a +1+ c+x;
当a>1时，c = ax+c+10^(i-1);
实现的代码如下：
public static int search(int _n) { int N = _n/10; int a1 = _n%10,a2; int x = 1; int ten = 10; int c = a1 == 0?0:1; while(N > 0) { a2 = N%10; if(a2 == 0); else if(a2 == 1)c = a1 + 1 + x + c; else c = a2*x + c + ten; a1 = 10*a1 + a2; N /=10; x = 10*x + ten; ten *= 10; } return c; }
而以上解法的时间复杂程度只有O(logN)
如果您路过这里，您有更好的解法吗？：）
页:
[1]