求1-N中十进制正整数1的个数

72 阅读 0 评论 48 点赞

我是靠谱客的博主碧蓝哈密瓜，最近开发中收集的这篇文章主要介绍求1-N中十进制正整数1的个数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述


 给你一个十进制的正整数N，求1-N所有数中出现“1”的的数目。

比如
	N=2： 1    2 ，1的个数的1.
	N=5： 1   2  3  4  5  ，1的个数是1。
	N=12：1  2   3  4  5  6  7 8   9  10  11  12 ，1的个数是5.

希望你能写一个函数F（N），返回1-N之间出现1的个数，F（12）=5；
如何求得？
	遍历？对，是很容易想到。可是不能碰到什么问题就用遍历吧。不过还是把遍历解决一下，再想好办法。遍历每一个数，对每一个数求1的个数，然后加起来得和。每一个数的1的个数和每一位有关系？如何求每一位的值？对每个数求余，得到个位数，其他位呢？不好求吧。	可是我们对这个数再求整，相当于把个位数扔掉，那么其他位就落到各位。求解方法一样。也就是说对每个数要先求余再求整然后不停的迭代，直到变为0。
Ok，编码实现

int Count1Integer(int n)//统计1-n中1的个数
{
int num=0;
for(int i=1;i<=n;i++)
{
for(int j=i;j>0;j/=10) //为什么要用for不是while,习惯吗？
{
if(j%10==1)
num++;
}
}
return num;
}

	时间复杂度是T(n)=O(n)*O(lg10n)=O(nlgn) 时间复杂度看起来还不错，可是我们还能优化吗？遍历总不是最好的办法，我们必须想办法如何去避免这个方法。
	好好想一想，有没有规律？有没有技巧来解决这种问题？不遍历每一个数，就像解决二进制中1的个数一样，我们可不可仅仅只遍历其位数呢？虽然略有不同，但原则上道理相通。不能学一个是一个，要举一反三的能力，要学会捕鱼的办法。
	我们可以试试，看看每一位上1的个数。
当n是一位数时：

	这没什么可分析位数的，因为只有一位数，f(n)仅仅由个位数决定。n=1 f(1)=1；n=2 f(2)=1；n=3 f(3)=1；n=4 f(4)=1；n=5 f(5)=1；n=6 f(6)=1；n=7 f(7)=1；n=8 f(8)=1；n=9 f(9)=1.这没什么可说的，只有一位数。
当n是两位数时：

	此时我们可以将一个正整数中1的个数分成两部分，一部分是位上出现1的数目f1(n)，一部分是十位上出现1的数目f2(n) 。
举一些代表性的数
	n=10：f(10)=f2(10)+f1(10)=1+1=2；
	n=11：f(11)=f2(11)+f1(11)=2+2=4；
	n=12：f(12)=f2(12)+f1(12)=3+2=5；
	n=13：f(13)=f2(13)+f1(13)=4+2=6；
	n=20：f(20)=f2(20)+f1(20)=10+2=12；
	n=21：f(21)=f2(21)+f1(21)=10+3=13；
	n=22：f(22)=f2(22)+f1(22)=10+3=13；
	n=23：f(23)=f2(23)+f1(23)=10+3=13；
	n=30：f(30)=f2(30)+f1(30)=10+3=13；
	n=31：f(31)=f2(31)+f1(31)=10+4=14；
	n=32：f(32)=f2(32)+f1(32)=10+4=14；
	n=33：f(33)=f2(33)+f1(33)=10+4=14；
	能看出什么门道吗？
先来看看十位：
当十位上的数为1的时候：
	n=10：f(10)=f2(10)+f1(10)=1+1=2；
	n=11：f(11)=f2(11)+f1(11)=2+2=4；
	n=12：f(12)=f2(12)+f1(12)=3+2=5；
	n=13：f(13)=f2(13)+f1(13)=4+2=6；
从这些数中，可以看出十位上1的数目仅仅由个位所决定，也就是个位当前数+1.
当十位上的数为大于1的时候：
	n=20：f(20)=f2(20)+f1(20)=10+2=12；
	n=21：f(21)=f2(21)+f1(21)=10+3=13；
	n=22：f(22)=f2(22)+f1(22)=10+3=13；
	n=23：f(23)=f2(23)+f1(23)=10+3=13；
	n=30：f(30)=f2(30)+f1(30)=10+3=13；
	n=31：f(31)=f2(31)+f1(31)=10+4=14；
	n=32：f(32)=f2(32)+f1(32)=10+4=14；
	n=33：f(33)=f2(33)+f1(33)=10+4=14；
十位上1的数目都是10，也就是说此时十位上1的数目仅仅和十位有关系，也就是十位的位因子10.
再来看看个位：
当个位上的数是1的时候：
	n=11：f(11)=f2(11)+f1(11)=2+2=4；
	n=21：f(21)=f2(21)+f1(21)=10+3=13；
	n=31：f(31)=f2(31)+f1(31)=10+4=14；
此时影响个位1的数目的就是十位，也就是十位当前数+1。


当个位上的数大于1的时候：
	n=22：f(22)=f2(22)+f1(22)=10+3=13；
	n=23：f(23)=f2(23)+f1(23)=10+3=13；
	n=32：f(32)=f2(32)+f1(32)=10+4=14；
	n=33：f(33)=f2(33)+f1(33)=10+4=14；
此时影响个位上1的数目的就是十位，也就是十位当前数+1。


还有当个位上的数等于0时：
	n=10：f(10)=f2(10)+f1(10)=1+1=2；
	n=20：f(20)=f2(20)+f1(20)=10+2=12；
	n=30：f(30)=f2(30)+f1(30)=10+3=13；
此时影响个位上1的数目的事就是十位，也就是十位当前数。
	看起来可以分类写代码了，可是真的是这样的规律吗？
	其实，这样分析是有漏洞的。因为我们只分析了两位数，分析的时候只有2位。当分析个位的时候，仅仅分析了十位，也就是高位，尽管个位是最低位，我们也不能忽略低位。如果分析的是中间位，两边都有的时候规律就不一定是这样了。同样的道理，我们分析十位的时候仅仅分析了个位，尽管没有百位，我们也要分析。而且我们分析十位的时候并没有考虑十位为0的情况，出现了百位，十位上的数就可能为0。
	所以为了使规律更加的客观，还有要检验刚才的分析结果。我们需要去分析一些三位数，可是为了保险起见，我们分析一些五位数。这样我们去分析百位的时候高位和低位上的数就不仅仅是一位了，这样也更加的客观一些。
	由于刚才的分析我们了解到每一位上的1的数目分三类情况，也就是当前位为=0、=1、>1。我们仅仅分析一下百位：
	当百位上的数字是0的时候，假设n=12013。此时百位上出现1的数是100-199，1100-1199，2100-2199……11100-11199.也就是12个100，12*100=1200个。也就是说此时百位上1的数目是由高位（12）决定的，而且等于高位（12）*当前位因子（100）。
	当百位上的数字是1的时候，假设n=12113.此时百位上出现1的数是100-199，1100-1199，2100-2199……11100-11199，12100-12113。12*100+13+1=1214.此时百位上1的数位不仅由高位(12)决定，也和低位(13)有关系，而且等于高位(12)*当前位因子(100)+低位(13)+1。
	当百位上的数字大于1的时候，假设n=12213.此时百位上出现1的数是100-199，1100-1199，2100-2199……11100-11199，12100-12199。(12+1)*100=1300 。此时百位上1的个数还是仅仅由高位（12）决定，而且等于(高位(12)+1)*当前位因子。
	这样才是没有漏洞、好的分析结果。这样就可以写代码了。关键问题解决了，还有一个小问题就是如何求一个数的高位和低位，还有当前位。这和当前位的位因子有关系。
	如何求的呢？对于12345，假设当前位是百位，则当前位的数字是3，高位是12，低位是45。如何得来的呢？无非就是一些求整求余加减乘除的事情。求低位利用高位和当前位，12345-（12345/100）*100=45.。求高位直接求即可，12345/100=123？12345/(100*10)12.
而求当前位，12345/100=123，123%10=3.

Ok，是时候编码实现了：

int Count1Integer(int n)//统计1-n中1的个数
{
int num=0;
int LowerNum=0;//当前位的低位的数字
int CurNum=0;
//当前位的数字
int HigherNum=0;
//当前位的低位的数字
for(int factor=1;factor<=n;factor*=10)//位因子
初始个位因子是1
{
LowerNum=n-(n/factor)*factor;
CurNum=(n/factor)%10;
HigherNum=n/(factor*10);
if(CurNum==0)
{
num+=HigherNum*factor;
}
else if(CurNum==1)
{
num+=HigherNum*factor+LowerNum+1;
}
else
{
num+=(HigherNum+1)*factor;
}
}
return num;
}


	时间复杂度就是n的位数。T(n)=O(log10n+1)=O(lgn)，比刚才的遍历要好太多了。如果不相信这个规律，可以利用刚才的遍历方法来验证一下。验证结果是一致的。
	这个问题就暂时解决了。
	我问你，对于一个32位的正整数，满足f(n)==n的最大的n是多少？很简单，利用刚才的函数就可以解决。可是如果是理论证明呢？有必要吗？暂略。
我再问你，如果是一个二进制数呢？如何求1-N中所有出现的1呢？遍历当然可以。这里，可以利用刚才的方法寻找规律。f(1)=1,f(10)=10,f(11)=100.(这些数都是二进制表示)我尝试了一下找规律，发现没有什么规律可循。。一部分数是这个规律，另一些数是那个规律。总有数不符合规律。