求解一算法题~~~要求考虑效率

Question

有这样一个函数f(n)，对于任意正整数n，它表示从 0 到 n 之间出现“1”的个数， 
比如   f(1)=1, f(13)=6, 请列出从 1 到 1234567890 中所有的 f(n) = n的n,要求准确快速.

Answer 1

f(n) 表示 0~n 中 数字带有1的数字个数

Answer 2

import java.util.regex.Matcher;
import java.util.regex.Pattern;
 public class NumCount{
  int num;
  int total=0;
    public NumCount(int num){
     this.num=num;
  }
  public int getTotal(){
  Pattern p=Pattern.compile("1");
  if(num<=0)
  return 0;
  else{
  for(int i=1;i<=num;i++){
       Matcher match=p.matcher(String.valueOf(i));
       while(match.find()){
    total++;
  }
  }
  return total;
  }
  }
 
  public static void main (String[] args) {
      NumCount t=new NumCount(111);
       System.out.println ("1的个数："+t.getTotal());
    }
 }

Answer 3

这个是数字计算的
import java.lang.Math;
public class NumCount{
private int num;
private int total=0;
public NumCount(int num){
this.num=num;
}
public int getTotal(){
if(num<=0)
return 0;
else{
for(int i=1;i<=num;i++){
int tem=i;
      String str=String.valueOf(i);
int len=str.length();
for(int j=len-1;j>=0;j--){
if((int)(tem/(int)Math.pow(10,j))==1)
                       total++;
                       if(j+1>1){
                          tem=tem%((int)Math.pow(10,(j==0)?1:j));   
                        }    
}
}
return total;
}
}
public static void main (String[] args) {
NumCount n=new NumCount(21);
System.out.println ("1的个数："+n.getTotal());
        }
}

Answer 4

3,4楼两个算法速度都不行~
n值可能很大 比如1234567890，for(int i=1;i <=n;i++)出现这句肯定不正确

Answer 5

相信很多人都能立刻得出以下的解法：  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代码 
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;      
}      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)

Answer 6

这个好
总结了下
1234 中的十位的个数：十位3> 1 ;(12 + 1) * 10
         百位的个数：百位2> 1; (1 + 1) * 100
         个位的个数: 个位4>1; (123 + 1) *1
         千位的个数: 千位1 ; 234 + 1
等于 130 + 200 + 124 + 235 =....
这样应该是最快的