0%

LeetCode: Single Number III

还不错的一道题

首先,很多人都想到,要将全部数都异或,结果为diff。diff则是这两个单独数的异或值。

然后,我们可以知道,diff不为0,则可以从diff中挑选一个非零的位,假设为k。然后将全部数分为两部分,一部分是第k位为0的,一部分是第k位为1的。这里有个技巧,就是如果diff和 -diff按位取与,则结果只有一位为1,这一位是diff的最低非零位。我们可以知道,两个单独数肯定是分别位于不同的部分。

最后,就是将两部分各自取异或。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int diff = 0;
for(int i: nums)
diff ^= i;
diff &= -diff;
vector<int> ret = {0, 0};
for(int i: nums)
{
if(i&diff)
ret[0]^=i;
else
ret[1]^=i;
}
return ret;
}
};