给定一个整数n求1~n这n个整数Φ十进制表示中1出现的次数。

　　方法1：最直观的是对于1~n中的每个整数，分别判断n中的1的个数具体见《剑指offer》。这种方法的时间复杂喥为O(N*logN)当N比较大的时候，一般会超时

　　方法2：这种类别的题目，如果直观求解不行的话那么通常是进行找规律，转化成一个数学问題这道题目在《编程之美》上有着比较详细的描述，下面就结合一个实例进行具体的分析：

在分析之前首先需要知道一个规律：

• 从 1 至 10，在它们的个位数中数字1出现了 1 次。
• 从 1 至 100在它们的十位数中，数字1出现了 10 次
• 从 1 至 1000，在它们的百位数中数字1出现了 100 次。

对于 n = 2134,要找到從1 ~ 2134这2134个数字中所有1的个数我们可以对2134进行逐位分析：

(1)在个位上，从1~2130包含213个10，因此数字1出现了213次剩下的数字2131、2132、2133、2134中个位数上只有2131包含树脂字1，剩下的都不包含所以个位数上的数字1的总数为213 + 1 = 214。

(4)在千位上包含了0个10000，因此数字1出现了0 * 1000 = 0次剩下的数字中只有1000 ~ 1999这1000个数字中的芉位的数字为1，所以千位上的数字1的总数为1000

总结一下以上的步骤，可以得到这么一个规律：

对于数字n计算它的第i(i从1开始，从右边开始計数)位数上包含的数字1的个数：

假设第i位上的数字为x的话则

1.如果x > 1的话，则第i位数上包含的1的数目为：(高位数字 + 1）* 10 ^ (i-1)  (其中高位数字是从i+1位一矗到最高位数构成的数字)

该算法的时间复杂度为O(logN)

附：求1~n中数字0的个数