a*******y
发帖数: 1040 | 1 Given an array of 32bit unsigned integers in which every number appears
exactly twice except three of them, find those three numbers in O(n) time
using O(1) extra space. The input array is read-only. What if there are k
exceptions instead of 3? |
c****x
发帖数: 15 | 2 I don't think XOR can solve it.
Linear sort like Radix sort is enough |
h*****3
发帖数: 1391 | |
a*******y
发帖数: 1040 | 4 k是奇数怎么搞
比如k是3，set的bit是1的话，三个数在这个位置上可能是0，0，1， 也可能是1 1 1，
这个怎么搞？ |
h*****3
发帖数: 1391 | 5 喔，那我理解错了，我还以为是array里面有1个数重复3遍呢。
1）那这个xor以后，res1;
2) 比如说最后一个bit是1的话，再XOR扫描一遍最后一个bit是1的数，如果结果和前面
一次的相等，那就是1，1，1，如果不等，那有个数就找出来了。设为a
3）a xor res1，那其他2个数的差别就出来了。
4)如果是1，1，1的话，就找res1中的下个1，再repeat 2）；如果res1中没1了，bit为
0的话，不就是有2个0，一个1，或者2个1，一个0吗？xor一遍该位为1的，如果为1，那
就是第一种情况，如果为0，那就是第二种情况，再xor一遍该位为0的，反正能找出一
个数出来。然后repeat 3 就可以了。 |
a*******y
发帖数: 1040 | 6 如果res1中没1了，bit为
这句不对，应该是三个0或者1，1，0，
还有一种情况就是，你都试过了所有的位置了都不行，那么就是这三个数都是一样的 |
h*****3
发帖数: 1391 | 7 我糊涂了，0 xor 0 = 1; 1 xor 0 = 1;
怎么会3个0？
还有，如果3个数都一样的，也就是说有2个数的相对位置是完全pair的，那和题目中有
3个数不一样岂不是矛盾了？
【在 a*******y 的大作中提到】
: 如果res1中没1了，bit为
: 这句不对，应该是三个0或者1，1，0，
: 还有一种情况就是，你都试过了所有的位置了都不行，那么就是这三个数都是一样的
|
a*******y
发帖数: 1040 | 8 how is 0 xor 0 is 1?
it does not say the three number cannot be the same, only say it does not
appear twice, so maybe three times
【在 h*****3 的大作中提到】
: 我糊涂了，0 xor 0 = 1; 1 xor 0 = 1;
: 怎么会3个0？
: 还有，如果3个数都一样的，也就是说有2个数的相对位置是完全pair的，那和题目中有
: 3个数不一样岂不是矛盾了？
|
h*****3
发帖数: 1391 | 9 嗯。你是对的
【在 a*******y 的大作中提到】
: how is 0 xor 0 is 1?
: it does not say the three number cannot be the same, only say it does not
: appear twice, so maybe three times
|
