黑马程序员技术交流社区
标题:
来一道题
[打印本页]
作者:
东大小宇哥
时间:
2015-5-16 19:45
标题:
来一道题
1~100共一百个自然数，放入一个99个元素的数组a[99]，要求写出一个尽量简单的方案，找出没有被放入数组的这个数
作者:
南山忆
时间:
2015-5-16 20:10
按自己规定方吗？
作者:
xbutterflyx
时间:
2015-5-16 20:26
怎么放?楼主?随便放?
作者:
开弓没有回头箭
时间:
2015-5-16 20:43
最方便的方法是讲a[99]数组中的书全加起来，用5050（1-100相加的和）去减，所得的值就是差的那个
作者:
黄冬
时间:
2015-5-16 21:26
开弓没有回头箭 发表于 2015-5-16 20:43
最方便的方法是讲a[99]数组中的书全加起来，用5050（1-100相加的和）去减，所得的值就是差的那个 ...
这个办法貌似可行。。。
作者:
1017161726
时间:
2015-5-16 23:00
这个还是二分思想最简单了。如果求和的话，都相当于从1遍历了。
作者:
我干阿衰
时间:
2015-5-16 23:05
怎么放??
作者:
1017161726
时间:
2015-5-16 23:13
仔细分析了下，如果是全部相加，就要遍历每个元素，那不如直接查找了。
数组长度 int L = arr.length=99，
取最中间的角标，mid = L/2-1=48，
判断 arr[mid]==49，
如果不等于49，缺少的那个元素就在前半部分，
然后 mid /=2，
判断 arr[mid]==mid+1,
这样的方法越是到最后范围很小的时候，越显得冗余，
所以最好范围的长度控制在5左右了就开始遍历，这样最快了。
因为你的数组长度还是很小，怎么算都没差别，
如果长度几千几万的，这个方法的便捷就显现出来了。
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2