從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.2cto.com     return res;   }   int main()   {       int n;       while (scanf("%d",&n)!=EOF)       {           printf("%d\n",function(n));       }       return 0;   }