频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
0..n去掉一个数,给你剩下的数,找出去掉的那个数
2013-09-05 08:58:06           
收藏   我要投稿
首先,考虑没有去掉那些数,如果n是奇数,n+1个最低位肯定是0101...01,count(0)=count(1),如果n是偶数,0101...010那么0要比1多一个,count(0)=count(1)+1

例子n=4

0=00 1=01 2=10 3=11 4=100,最低位有3个02个1,

所以规律是,如果没有去掉一个数时,count(0)=count(1)+[0,1], 如果去掉的数最低位是0,即count(0)-1,那么count(1)>=count(0).

如果去掉的是1,count(1)-1,那么count(0)>=count(1)+1

这是两种不同的情况,我们根据这个规律推算去掉的数最低位是啥。统计剩下的n个数最低位0和1的个数:

如果count(1)>=count(0) ,那么去掉的是0

如果count(0)>count(1) ,那么去掉的是1

然后接下来,确定倒数第二位。我们尽量使得倒数第二位能和倒数第一位那样推导。

如果最低位是0,那么我们把所有是最低位是1的数全部去掉,剩下的全是最低位为0的,如果剩下的数全部右移一位将最低位去掉,那么正好就和上面的情况一样了。

如果最低位是1,那么我们把所有是最低位是0的数全部去掉,剩下的全是最低位为1的,右移一位,也正好是和上面的情况一样了。

举个例子:

0,1,2,3,4,5,6,7 将最低位为0的去掉就剩下1,3,5,7 其实相当于是隔一个数删一个数,再右移一位(除以2),得到0,1,2,3,如果去掉的是5,那么剩下的是0,1,3. 这个正好是0到n/2中去掉了一个数,找出那个数来。这样就可以用上面的方法找到倒数第二位了。

还是这个例子,0~7,去掉了3:

0. 输入是0,1,2,4,5,6,7

1.先得到count(0)>count(1) 所以最低位是1

2.去掉最低位是0的,剩下1,5,7, 然后右移一位,0,2,3

3. 输入变为0,2,3, 回到第一步

这样依次得到1,1,0,这个是最低位最先算,所以结果就是011=3

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 个数
上一篇:MyEclipse注释模板设置
下一篇: Gitolite v3安装配置指南
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站