问题描写叙述：

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。比如输入12，从1到12这些整数中包括1 的数字有1。10。11和12。1一共出现了5次。

这是一道广为流传的google面试题。

算法：

第一种思路：对从1到n的每一个数进行统计，统计的结果相加。算法复杂度为O(n)

另外一种思路：举例说明。

令n=321。则：

它的个位上出现1的形式为XY1，次数和为33（由于十位百位上可能出现的组合为0-32）

它的十位上出现1的次数和较为复杂，形式为X1Y，X的取值范围为0-3。Y的取值范围为0-9。所以X1Y一共同拥有40中形式，即1在十位出现次数和为40

它的百位上出现1的形式为1XY显然，XY的取值范围为00-99。所以次数和为100

故总和为100+40+33=173

经过分析，我们能够的到一个一般化的公式：

一个digit位的数n，从右数第i位（i从0開始）上出现1的次数和为：（i+1位到digit-1位的组合数+1）*10的i次方

数学表达为

count(i)=[n/pow(10,i+1)+1]*pow(10,i)

sum=∑count(i)

由于位数digit=[logn]+1   (当中logn为向下取整），所以时间复杂度为O(logn)

代码实现：

第一种思路：

#pragma once

#include<iostream>

using namespace std;

int Find(int m)

{

	int sum = 0;

	while (m > 0)

	{

		int temp;

		temp = m % 10;

		if (temp == 1)

			sum += 1;

		m = m / 10;

	}

	return sum;

}

int Count(int n)

{

	int sum = 0;

	for (int i = 1; i <= n; i++)

		sum += Find(i);

	return sum;

}

void  main()

{

	int n;

	cin >> n;

	Count(n);

	cout << Count(n) << endl;

	system("pause");

}

另外一种思路：

#pragma once

#include<iostream>

#include"math.h"

using namespace std;

int Count(int list[], int n,int digit)

{

	int sum = 0;

	for (int i = 0; i < digit; i++)

		sum += (int(n / pow(10, i + 1)) + 1)*(int)pow(10, i);

	return sum;

}

void  main()

{

	int n;

	cin >> n;

	int temp = n;

	int digit = 1;//n的位数

	while (temp > 0)

	{

		if (temp - temp % 10 > 0)

			digit++;

		temp = temp / 10;

	}

	int* list = new int[digit];//list[i]中是n从右边第i位上的数字

	for (int i = 0; i < digit; i++)

		list[i] = (n - int(n%(int)pow(10, i))) / (int)pow(10, i) % 10;

	cout << Count(list, n,digit) << endl;

	system("pause");

}