发布时间 : 星期日 文章计算从1到N的所有整数中包含数字1的个数更新完毕开始阅读
计算从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表示为a[n]a[n-1]...a[1]，其中a[i](1<=i<=n)表示N的各位数上的数字。
c[i]表示从整数1到整数a[i]...a[1]中包含数字1的个数。
x[i]表示从整数1到10^i - 1中包含数字1的个数，例如，x[1]表示从1到9的个数，结果为1；x[2]表示从1到99的个数，结果为20； 当a[1]=0时，c[1] = 0;
当a[1]=1时，c[1] = 1; 当a[1]>1时，c[1] = 1;
当a[2]=1时，c[2] = a[1] +1+ c[1] + x[1]; 当a[2]>1时，c[2] = a[2]*x[1]+c[1]+10;
当a[3]=1时，c[3] = a[2]*a[1] +1+ c[2] + x[2]; 当a[3]>1时，c[3] = a[3]*x[2]+c[2]+10^2; ...... 以此类推
当a[i]=1时，c[i] = a[i-1]*...*a[1] +1+ c[i-1]+x[i-1]; 当a[i]>1时，c[i] = a[i]x[i-1]+c[i-1]+10^(i-1);
实现的代码如下： Java代码
1. public static int search(int _n) 2. {
3. int N = _n/10; 4. int a1 = _n,a2; 5. int x = 1; 6. int ten = 10;
7. int c = a1 == 0?0:1; 8. while(N > 0) 9. {
10. a2 = N; 11. if(a2 == 0);
12. else if(a2 == 1)c = a1 + 1 + x + c;
13. else c = a2*x + c + ten; 14. a1 = 10*a1 + a2; 15. N /=10;
16. x = 10*x + ten; 17. ten *= 10; 18. }
19. return c; 20.}
而以上解法的时间复杂程度只有O(logN)
今天看到一道有趣的算法题，题目如下： 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表示为a[n]a[n-1]...a[1]，其中a[i](1<=i<=n)表示N的各位数上的数字。 c[i]表示从整数1到整数a[i]...a[1]中包含数字1的个数。 x[i]表示从整数1到10^i - 1中包含数字1的个数，例如，x[1]表示从 ...
计算JAVA 在0~N之间出现“1”的个数
有这样一个函数f(n),对于任意正整数n,它表示从 0 到 n 之间出现“1”的个数,比如 f(1) = 1, f(13) = 6,请列出从 1 到 1234567890 中所有的 f(n) = n 的n, 要求准确快速. 相信很多人都能立刻得出以下的解法： for(n:N)
{
判断n包含1的个数; 累加计数器; }
这是最直接的解法，但遗憾的是，时间复杂程度为O(N*logN)。因为还需要循环判断当前的n的各位数，该判断的时间复杂程度为O(logN)。
接下来就应该思考效率更高的解法了。说实话，这道题让我想起另外一道简单的算法题： N为正整数，计算从1到N的整数和。
很多人都采用了循环求解。然后利用初等数学知识就知道S=N*(N+1)/2，所以用O(1)的时间就可以处理。
再回到本道题目，同理应该去寻找到结果R与N之间的映射关系。 分析如下：
假设N表示为a[n]a[n-1]...a[1]，其中a[i](1<=i<=n)表示N的各位数上的数字。 c[i]表示从整数1到整数a[i]...a[1]中包含数字1的个数。
x[i]表示从整数1到10^i - 1中包含数字1的个数，例如，x[1]表示从1到9的个数，结果为1;x[2]表示从1到99的个数，结果为20; 当a[1]=0时，c[1] = 0; 当a[1]=1时，c[1] = 1; 当a[1]>1时，c[1] = 1;
当a[2]=1时，c[2] = a[1] +1+ c[1] + x[1]; 当a[2]>1时，c[2] = a[2]*x[1]+c[1]+10;