g*******y
发帖数: 1930 | 1 网上看来的：
一堆数，其中一些数出现了一次，一些数出现了两次，只有一个数出现了三次
找出那个出现了3次的数
hash方法很trivial就不说了。
如果用bitwise operator，怎么高效的做？除了XOR，是不是还得用点别的办法？ | a*****e
发帖数: 51 | 2 (1) Sorting, time: O(nlogn), space: O(1)
(2) Hashing, time: O(n), space: O(n)
(3) Bitwise operation, How can you use XOR, since after XORing every
elements, both those elements which occur 1 time and the one occurring 3
times will be left indistinguishable?
【在 g*******y 的大作中提到】
: 网上看来的：
: 一堆数，其中一些数出现了一次，一些数出现了两次，只有一个数出现了三次
: 找出那个出现了3次的数
: hash方法很trivial就不说了。
: 如果用bitwise operator，怎么高效的做？除了XOR，是不是还得用点别的办法？
| g*******y
发帖数: 1930 | 3 我也是这样想的。
我觉得更大的可能是，发这个题出来的人，没有理解清楚或者是没有把题讲完整。
不过我还是抱着侥幸心理，万一有某个牛人能够用非常巧妙的方法做出来呢。。。
【在 a*****e 的大作中提到】
: (1) Sorting, time: O(nlogn), space: O(1)
: (2) Hashing, time: O(n), space: O(n)
: (3) Bitwise operation, How can you use XOR, since after XORing every
: elements, both those elements which occur 1 time and the one occurring 3
: times will be left indistinguishable?
| f*********r
发帖数: 68 | 4 try xor with counting approches. | a******h
发帖数: 19 | 5 Use two bit vector.
If two bits are set in both vector, this is the third appearance. |
|
