1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int[] singleNumber(int[] nums) {
int xorAns = 0;
for (int num : nums) {
xorAns ^= num;
}
int diff = xorAns & (-xorAns), ans1 = 0;
for (int num : nums) {
if ((num & diff) != 0) {
ans1 ^= num;
}
}
return new int[] { ans1, xorAns ^ ans1 };
}
}

这个方法太牛逼了.
我们先把所有的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)