剑指Offer--从1到n的整数中1出现的次数

暴力算法考虑数字规律的解法

暴力算法

对1到n的每一个数，使用while循环计算1 的个数，最后求和。 此方法时间复杂度为O(N*logN)，其中logN为数的位数。

考虑数字规律的解法

除了对每个数进行运算之外，还可以从数本身获取信息； 不能轻易看出的规律，那么先用一个简单的例子：21345，i表示第几位(从右往左)。 取i为第3位，则从i处将数分成两部分：a=213、b=45，现在计算第i位可能会有多少个1。 1）i>=2: 则1的个数有i左边的部分决定，一共有0~21共22种情况，而i位于百位，故有22100个1； 2）i=1： 则1的个数由i左边和右边部分共同决定，以为当i左边为22时，i位为1的个数不足100，不足的部分需由右边部分决定，从而有21100+45+1个1。 3）i=0： 当i的右边部分为22时，i位无法为1，故有21*100个1.

用代码表示为

int Number1OfN(unsigned int n){ int sum=0; int nLeft-0,nRight=0; for(int i=1;i<=n;i*=10){ nLeft=n/i; nRight=n%i; sum+=(nLeft+8)/10+(a%10==1)*(nRight+1); } return sum; }

nLeft+8用于判断第i位是否需要进位： i>=2: (nLeft+8)/10=nLeft+1; i=1&&i=0:(nLeft+8)/10=nLeft;