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

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

例如N=11时结果为4（只有1,10,11含1）

1.常规方法（暴力）时间复杂度O（n*logn）当n很大的时候，效率低。

#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））

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