从1到n之间的数字1出现的次数

例如N=11时结果为4（只有1,10,11含1）
1.常规方法（暴力）时间复杂度O（n*logn）当n很大的时候，效率低。
[cpp]  
#include <iostream>  
#include <cstdio>  
using namespace std;  
  
int function (int n)  
{  
    int count=0;  
    for (int i=1 ;i<=n;i++)  
    {  
        int j = i;  
        while (j)  
        {  
            if (j%10==1)  
                count++;  
            j/=10;  
        }  
    }  
    return count;  
}  
int main ()  
{  
    int n;  
    while (scanf ("%d",&n)!=EOF)  
    {  
        printf ("%d\n", function(n));  
    }  
    return 0;  
}  
 
2.编程之美上解法（时间复杂度O（logn））
[cpp]  
#include <iostream>  
#include <cstdio>  
using namespace std;  
  
int function (int n)//按照每一位出现1的次数来进行计算  
{  
    int factor =1 ;//factor 是该位的权值  
    int res = 0;  
    int low, cur, high;  
    while (n / factor)  
    {  
        low = n % factor;//数字的低位  
        cur = n / factor % 10;//数字当前位置的数  
        high = n / factor / 10;//数字的最高位  
        if (cur==0)  
            res += high * factor;  
        else if(cur==1)  
            res += high * factor + low + 1;  
        else   
            res += (high + 1) * factor;  
        factor *= 10;  
    }  www.zzzyk.com
    return res;  
}  
int main()  
{  
    int n;  
    while (scanf("%d",&n)!=EOF)  
    {  
        printf("%d\n",function(n));  
    }  
    return 0;  
}

补充：软件开发 , C++ ,