腾讯的面试题,谁来挑战下

有一组数字,从1到n,从中减少了3个数,顺序也被打乱,放在一个n-3的数组里

请找出丢失的数字,最好能有程序,最好算法比较快
假设n=10000

作者: easyuu   发布时间: 2011-12-28

PHP实现的话,生成体积为N的数组array[n-1]; 然后foreach($n_array as $key) {移除array[$key]}; printr($array);

好吧,偶是菜鸟,取巧了。

作者: coosh   发布时间: 2011-12-28

修正一下,生成array[n],然后把array[0]忽略掉,后面的一样。

引用 1 楼 coosh 的回复:

PHP实现的话,生成体积为N的数组array[n-1]; 然后foreach($n_array as $key) {移除array[$key]}; printr($array);

好吧,偶是菜鸟,取巧了。

作者: coosh   发布时间: 2011-12-28

引用 2 楼 coosh 的回复:

修正一下,生成array[n],然后把array[0]忽略掉,后面的一样。

引用 1 楼 coosh 的回复:

PHP实现的话,生成体积为N的数组array[n-1]; 然后foreach($n_array as $key) {移除array[$key]}; printr($array);

好吧,偶是菜鸟,取巧了。

擦,这里是JS专区啊

作者: easyuu   发布时间: 2011-12-28

先排序,然后用二分查找法做,应该比较快
n=10000 第一次查找是5000 
if n[4999]=5000
那缺失的3个数字肯定就在后半部分
if n[4999]<5000
证明前面肯定有缺失的数字
以此类推

作者: javascript_2011   发布时间: 2011-12-28