260. Single Number III
1 | class Solution { |
这个方法太牛逼了.
我们先把所有的num都xor一遍, 得到xorAns, 它就是两个unique nums的xor的结果. 其中两个num bit不一样的位置在xorAns的对应位置是1, 一样的位置则是0.
那么是1的位置怎么知道是谁的1, 是0的位置如何知道一样的是0还是1互相抵消了.
这个方法能够知道1的位置是谁的1. 我们取xorAns中最右边是1的bit, 把它孤立出来, 我们可以用num & (-num)来完成. 此时我们在开始把所有的num给xor一遍, 然而这次只有被孤立出来的这个bit的位置是1的num才能有资格xor. 于是uniquenum中这一位是1的肯定能入选, 其次其他重复的数字中可能这一bit也有是1的, 但是没关系, 这些数字会出现两次, 因此就会被抵消. 最后得到的就是unique num中这一位是1的那个num, 那另一个num就是xorAns和这个得出的num xor一下就行了.
我只能说绝了.
时间复杂度: O(n)
空间复杂度: O(1)