【编程之美】读书笔记：求1到N之间整数中出现1的个数

问题：给定一个十进制正整数N，写下从1开始到N的所有整数，求其中出现的所有“1”的个数？例如：N=2，写下1,2.1的个数为1。当N=12,1的个数为5。

解法一：从1开始遍历到N,将其中每一个数中含有1的个数加起来，得到从1到N的所有1的个数之和。

 int Count1InInteger(int n){   int iNum=0;   while(n!=0)  {   iNum+=(n%10==1)?1:0;   n/=10;}return iNum;}int f(int n){int iCount=0;for(int i=1;i<=n;i++){iCount+=Count1InInteger(i)}return iCount;}

这个算法的时间复杂度为：O(N)*计算每个整数里面“1”的个数的复杂度=O(N*logN);当N非常大的时候，该时间复杂度以超过线性的速度增长。

解法二：假设N=abcde,这里a,b,c,d,e分别是十进制数N的各个位数上的数字。如果要计算百位上出现1的次数，它会受到三个因素影响：百位数上的数字，百位以下的数字，百位以上的数字。

a、如果百位上的数字为0，则百位出现1的次数由更高位决定。如12013，则可以知道百位出现1的情况可能是100~119,1100~1199,2100~2199，。。，11100~11199，一共1200个。也就是由更高位数字(12)决定，并且等于更高位数字(12)*当前位数(100);
b、如果百位上数字为1,则百位上出现1的次数由更高位和低位共同决定。例如对于12113,受高位的影响百位出现1的个数为等于更高位数字(12)*当前位数(100)=1200.但是它还受低位影响，等于低位数字(113)+1;
c、如果百位上的数字大于1(即为2-9)，则百位出现1的次数仅由更高位决定，比如12213，等于更高位数字+1（12+1）*当前位数(100)=1300.

通过分析，得出如下代码：

 int Sum1s(int n){int iFactor=1;int iLowerNum=0;int iCurrNum=0;int iHigherNum=0;while(n/iFactor!=0){iLowerNum=n-(n/iFactor)*iFactor;iCurrNum=(n/iFactor)%10;iHigherNum=n/(iFactor*10);switch(iCurrNum){case 0:iCount+=iHigherNum*iFactor;break;case 1:iCount+=iHigherNum*iFactor+iLowerNum+1;break;default:  iCount+=(iHigherNum+1)*iFactor;break;}iFactor*=10;}return iCount;}

该算法的时间复杂度为O(Len),Len为数字N的长度。