人人网笔试题一道，小菜求解

zz8880

乱序存储10个大小连续的自然数（如6,1,2,3,9,4,5,7,0,8）中随机抽取一个，根据余下的数，如何判定被抽取数的值？如果有1000万或更多自然数时，判定被抽取数的值时，也用同样的方法吗？

xfxfxy

sum

wangzhen11aaa

如果先比较分半，前部相减如果等于0，就算后面的的(就是全部的1/4)相减，再测试。
如果不等于0，就算出来了。最坏的情况是时间度几乎和全部求和相减差不多。不过你可以加入 random来控制。
这样出现最坏的情况概率就低多了。
这样是不是比orignal sum - last sun
要快点。

greensnow

对每个数, 奇数减偶数, 记录下最大值和最小值, 最后计算, 复杂度O(n)

yulihua49

乱序存储10个大小连续的自然数（如6,1,2,3,9,4,5,7,0,8）中随机抽取一个，根据余下的数，如何判定被抽取数的 ...
zz8880 发表于 2011-10-28 13:05

    总和应该是45，少几被抽走的就是几，其他的算法相同。

marsbible

10个的简单，sum一遍就行了。
1000万个的，可以排序，nlog(n)+n。
或者不嫌费内存，用bitmap。
再或者使用异或的方法，先计算0到1000万的异或值，
在计算这个数组的异或值，然后将这两个结果再异或一把就行了。

yuansheng_1997

即使很多个数也可以用sum啊，最开始全部算一遍，每次抽取和插入的时候根本不用把所有的数都加一遍吧？

goubao198562

异或 不再给提示了  自己想啊

James_think

使用位图或许不错

xfxfxy

异或 不再给提示了  自己想啊
goubao198562 发表于 2011-10-28 16:48

    ----------------------------
哪位大哥给介绍下？不懂