1~100共一百个自然数，放入一个99个元素的数组a[99]，要求写出一个尽量简单的方案，找出没有被放入数组的这个数

按自己规定方吗？

怎么放?楼主?随便放?

最方便的方法是讲a[99]数组中的书全加起来，用5050（1-100相加的和）去减，所得的值就是差的那个

开弓没有回头箭 发表于 2015-5-16 20:43
最方便的方法是讲a[99]数组中的书全加起来，用5050（1-100相加的和）去减，所得的值就是差的那个 ...

这个办法貌似可行。。。

这个还是二分思想最简单了。如果求和的话，都相当于从1遍历了。

怎么放??

仔细分析了下，如果是全部相加，就要遍历每个元素，那不如直接查找了。
数组长度 int L = arr.length=99，
取最中间的角标，mid = L/2-1=48，
判断 arr[mid]==49，
如果不等于49，缺少的那个元素就在前半部分，
然后 mid /=2，
判断 arr[mid]==mid+1,
这样的方法越是到最后范围很小的时候，越显得冗余，
所以最好范围的长度控制在5左右了就开始遍历，这样最快了。

因为你的数组长度还是很小，怎么算都没差别，
如果长度几千几万的，这个方法的便捷就显现出来了。