f*******r
发帖数: 198 | 1 给2N+1个数，其中2N个是两两重复的，不用hash table用O（n)的时间找出那个不重复
的数 |
K****n
发帖数: 5970 | 2 没见过
能不能随机找其中一个数 a[k]
iterate其它所有 a[i] i!=k
如果a[i]
如果a[i]>a[k]，a[i]放右边儿
如果a[i]==a[k]，a[i]放中间儿
iterate完毕之后
如果中间儿没有东西，return a[k]
如果中间儿有东西，那么左边儿或者右边儿必有一个奇数一个偶数
对其中奇数的那一堆数重复以上过程
这样expected complexity 大约是 n+n/2+n/4点点点儿， 最后是O(N)。但是worst
case就不是了。 |
f*******r
发帖数: 198 | 3 恩如果是用这样randomized algorithm期望复杂度是O(n),但是我不知道面试时他说的O
(n)可不可以是这种。
【在 K****n 的大作中提到】
: 没见过
: 能不能随机找其中一个数 a[k]
: iterate其它所有 a[i] i!=k
: 如果a[i]: 如果a[i]>a[k]，a[i]放右边儿
: 如果a[i]==a[k]，a[i]放中间儿
: iterate完毕之后
: 如果中间儿没有东西，return a[k]
: 如果中间儿有东西，那么左边儿或者右边儿必有一个奇数一个偶数
: 对其中奇数的那一堆数重复以上过程
|
s*****t
发帖数: 737 | 4 just use xor, you'll get it
【在 f*******r 的大作中提到】
: 给2N+1个数，其中2N个是两两重复的，不用hash table用O（n)的时间找出那个不重复
: 的数
|
S*********r
发帖数: 42 | 5 Steps of an O(n) search:
1. Find max value (M) among all 2N+1 numbers
2. Use M-bit number and then reset it to zero
3. Mark the ith bit use XOR for any number i
4. Find non-zero bit and the corresponding number |
f*******r
发帖数: 198 | 6 great.
thx
【在 S*********r 的大作中提到】
: Steps of an O(n) search:
: 1. Find max value (M) among all 2N+1 numbers
: 2. Use M-bit number and then reset it to zero
: 3. Mark the ith bit use XOR for any number i
: 4. Find non-zero bit and the corresponding number
|
q******u
发帖数: 46 | 7 不是这么麻烦的...只需要
x=0;
for (int i=0; i
就完了，不用扫描两次。
【在 S*********r 的大作中提到】
: Steps of an O(n) search:
: 1. Find max value (M) among all 2N+1 numbers
: 2. Use M-bit number and then reset it to zero
: 3. Mark the ith bit use XOR for any number i
: 4. Find non-zero bit and the corresponding number
|
s*****t
发帖数: 737 | 8 M-bit number, are you sure?
why not just xor all the numbers?
【在 S*********r 的大作中提到】
: Steps of an O(n) search:
: 1. Find max value (M) among all 2N+1 numbers
: 2. Use M-bit number and then reset it to zero
: 3. Mark the ith bit use XOR for any number i
: 4. Find non-zero bit and the corresponding number
|
S*********r
发帖数: 42 | 9 you are absolutely right.
【在 q******u 的大作中提到】
: 不是这么麻烦的...只需要
: x=0;
: for (int i=0; i: 就完了，不用扫描两次。
|
d*j
发帖数: 13780 | 10 能解释一下吗？
怎么看都是 0 :(
【在 S*********r 的大作中提到】
: you are absolutely right.
|
|
|
s*******s
发帖数: 1568 | |
f******6
发帖数: 723 | 12 How to find out the bit that is not 0 in the last step? What if the single
number is N^2? Thanks |
c******n
发帖数: 49 | 13 nice.
【在 q******u 的大作中提到】
: 不是这么麻烦的...只需要
: x=0;
: for (int i=0; i: 就完了，不用扫描两次。
|
t**g
发帖数: 1164 | 14 一个弱智问题
^操作是不是都是针对非负整数?
【在 q******u 的大作中提到】
: 不是这么麻烦的...只需要
: x=0;
: for (int i=0; i: 就完了，不用扫描两次。
|
s*******e
发帖数: 432 | 15 XOR is communicative. So suppose you have x not repeated and all other
repeated then:
a1 XOR a2 ....XOR a2n+1 = x XOR (b1 XOR b1) XOR (bn XOR bn)
= x XOR 0 XOR 0 XOR 0 ....= x |
