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
|