l******n
发帖数: 9344 | 1 一个数列，有2个数出现奇数次，其他的数都是偶数次。找出这2个数，要求o(n)time
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite |
l****o
发帖数: 315 | 2 HashMap, 不存在的放进去，存在的拿出来，最后return keySet. 可行否？ |
p******9
发帖数: 47 | 3 假设出现奇数次的两个数为x和y，把所有数异或在一起，结果为r=x^y。因为x!=y，所
以r必有一位为1，即x和y这一位不一样。然后按这一位分成两组，每组则只有一个数出
现奇数次，剩下的事情就很容易了，直接异或就可以了 |
l****o
发帖数: 315 | 4 这方法好，学习了。
【在 p******9 的大作中提到】
: 假设出现奇数次的两个数为x和y，把所有数异或在一起，结果为r=x^y。因为x!=y，所
: 以r必有一位为1，即x和y这一位不一样。然后按这一位分成两组，每组则只有一个数出
: 现奇数次，剩下的事情就很容易了，直接异或就可以了
|
C***U
发帖数: 2406 | 5 hashtable?
不过应该有更巧妙的办法
【在 l******n 的大作中提到】
: 一个数列，有2个数出现奇数次，其他的数都是偶数次。找出这2个数，要求o(n)time
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
|
v**********r
发帖数: 40 | |
l*****a
发帖数: 559 | 7 hehaitao一百题里面有。
对于两个出现奇数次的数字，其二进制表示必有个bit不同。用这个bit把数列分成两组
，即简化为找一个出现奇数次的数字的问题。 |
h****t
发帖数: 184 | 8 对，还有一个更变态的 3个数出现一次 ， 找出这3个数的题目。
【在 l*****a 的大作中提到】
: hehaitao一百题里面有。
: 对于两个出现奇数次的数字，其二进制表示必有个bit不同。用这个bit把数列分成两组
: ，即简化为找一个出现奇数次的数字的问题。
|
e***s
发帖数: 799 | 9 我觉得只有这样才能算正确答案， Hashtable， Bitarray之类的都登不上台面啊...
【在 p******9 的大作中提到】
: 假设出现奇数次的两个数为x和y，把所有数异或在一起，结果为r=x^y。因为x!=y，所
: 以r必有一位为1，即x和y这一位不一样。然后按这一位分成两组，每组则只有一个数出
: 现奇数次，剩下的事情就很容易了，直接异或就可以了
|
f*****e
发帖数: 2992 | 10 先全部异或，肯定有一位不相同，根据这一位把数组分成两个子数组，然后对这两个子
数组分别异或。
【在 l******n 的大作中提到】
: 一个数列，有2个数出现奇数次，其他的数都是偶数次。找出这2个数，要求o(n)time
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
|
