google的那道面试题最快的方法应该是

cjaizss

计算第一位出现1的个数，计算第二位出现1的个数...
加起来

cjaizss

时间复杂度：对数级别

converse

方法我知道了,可是对数级别的复杂度是怎么得出的呢?
怎么也得遍历完所有的数据才能知道有多少个1吧?请指教下~~

cjaizss

...
那就是你还没有弄懂我的算罚
比方12：

1     2
1的个数
(2+1) + (1+((2>0)?:1:0)
按位计算出来的
所以是对数级别
不用遍历0-12

lmatt

我也是你那么想的.但我觉求f(n)的值并不是关键,而应该是求最大n的时候的算法.

lmatt

fun(long long m)
{
        char a[100];
        int n,i;
        long long k=0,x=m;
        sprintf(a,"%lld",m);
        n=strlen(a);
        for(i=0;i<n;i++)
        {
                x-=(a[i]-4*pow10(n-i-1);
                if(i!=0&&i!=n-1)
                {
                if(a[i]==49) k+=x+1+(n-1-i)*pow10(n-2-i);
                else if(a[i]!=4 k+=(a[i]-4*(n-1-i)*pow10(n-2-i)+pow10(n-1-i);
                else k+=0;
                }
                if(i==n-1) k+=a[i]==48?0:1;
                if(i==0)
                {
                        if(a[0]!=49) k+=pow10(n-1)+(a[0]-4*(n-1)*pow10(n-2);
                        else k+=1+(n-1)*pow10(n-2)+x;
                }
                if(a[0]==4 k=0;
                else if(n==1) k=1;
        }
        if(k==m) printf("%lld\n",k);

}

converse

>>按位计算出来的
这个方法跟用语言的api接口做出来有什么分别?

cjaizss

原帖由 converse 于 2006-4-4 13:16 发表
>>按位计算出来的
这个方法跟用语言的api接口做出来有什么分别?

算法和语言无关

converse

>>算法和语言无关
那请问有几个语言支持位操作呢?你这个对数级别复杂度的算法也许只有对支持位操作的语言成立吧?既然如此,就不能下结论说是对数级别的复杂度而应该加一个前提条件.

cjaizss

原帖由 converse 于 2006-4-4 13:30 发表
>>算法和语言无关
那请问有几个语言支持位操作呢?你这个对数级别复杂度的算法也许只有对支持位操作的语言成立吧?既然如此,就不能下结论说是对数级别的复杂度而应该加一个前提条件.

我没有用位操作，不过如果一个语言连/和%两个运算都不支持，我也就不说什么了，如果这两个都不支持，那么这道题目根本就做不出来，更谈不上好的算法