一道PROGRAMMER 笔试题目,征解

tutu007

新手上路
注册
2002-07-14
消息
511
荣誉分数
0
声望点数
0
Randomly take out a number from 1 - 1000, and disorder the rest 999 numbers. What is the best algorithm to find out which number is missing?
 
不知道这样是不是一个好的办法:

将这999个数加起来,被1-1000所有数的和“500500”减,得到的差就是missing的那个数。
 
我总觉得缺少一些限制条件,best的定义很含糊。
 
最初由 viv 发布
不知道这样是不是一个好的办法:

将这999个数加起来,被1-1000所有数的和“500500”减,得到的差就是missing的那个数。
smart
 
1-499 | 500-1000
然后逻辑思维跟viv那个建议一样
所有相加然后和对应的相减
运气好的话
可以在1-499里头找出,运气不好的话,就要O(n)来完成


nevermind了,发现条件里头有个disorder剩下的999,打乱了就不行了
 
VIVI's algorithm is really smart.
 
最初由 viv 发布
不知道这样是不是一个好的办法:

将这999个数加起来,被1-1000所有数的和“500500”减,得到的差就是missing的那个数。

优 化 一 下 :

把加/减运算改为XOR
 
Can this work out the missing number? Just wondering...
-----------------------------------------------------
把加/减运算改为XOR
------------------------------------------------------
 
最初由 Teddy 发布
Can this work out the missing number? Just wondering...
-----------------------------------------------------
把加/减运算改为XOR
------------------------------------------------------

Why don't you write a small program and give it a try?

I'd say, using "+/-", you answered an IQ question; using "XOR" is more like "algorithm".
 
最初由 Teddy 发布
Can this work out the missing number? Just wondering...
-----------------------------------------------------
把加/减运算改为XOR
------------------------------------------------------

Yes. First like computing the sum of 1 to 1000, you can compute the xor sum of 1 to 1000, because xor sum of 0 to (4n-1) is 0, so xor sum of 1 to 4n is 4n, therefore, xor sum of 1 to 1000 will be exactly 1000.

Then we can compute the xor sum of the 999 numbers and make the last xor operation with 1000, that is exactly the missing number.

The xor bit operation is supposed to be much faster than the add/substract operation. Also, we can save the precomputation time for the sum of 1 to 1000. (1000 is a magic number which is exactly 4n)

This xor solution can be better than the previous solution.
 
Great, thanks for your explanation, tutu007. The XOR method is much faster assuming "xor sum of 0 to (4n-1) is 0" is correct. I didn't learn this from my school.
 
后退
顶部