Single Number

大意

在一个数组中，有一个数字只出现了一次，其他的数字都出现了两次，求在O(1)的额外空间
和O(n)的额外时间内如何求出只出现一次的数字。

思路

对于出现两次的数字x,有如下的性质
xx=0x ^ x = 0

对所有的数字进行一次异或，最终剩下的数字就是那个只出现了一次的数字

code

C++ version

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (auto i : nums) {
            ans ^= i;
        }
        return ans;
    }
};

Single Number II

大意

在一个数组中，有一个数字只出现了一次，其他的数字都出现了3次，求在O(1)的额外空间和
O(n)的时间内如何求出只出现一次的数字。

思路

对于出现3次的数字，有如下的性质

$x&(~x) = 0, x^x = 0 $
对于下面的操作，进行三次的时候必然只会为0。

1
2
one = (one^i)&(~two);
two = (two^i)&(~one);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
x 0
0 x
0 0
``

## code

C++ version
```cpp
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;      
        for (auto i: nums) {
            one = (one^i)&(~two);
            two = (two^i)&(~one);
        }
        return one;
    }
};

Single Number III

大意

在一个数组中，有两个数字只出现了一次，其他的数字都出现了两次，求这两个数字

思路

假设我们那两个数字是A,BA, B,和第一问一样，我们直接进行全部数字的异或得到的就是ABA^B

对于ABA^B，我们可以得到最后一位为1的位置，即A和B的第一个不同的位置。。

对于数组里面的全部数字，根据次位是否为1来进行分别异或。

code

C++ version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long sumxor = 0;
        for (auto i: nums) sumxor ^= i;
        sumxor = (sumxor & ~sumxor);
        int ans1 = 0, ans2 = 0;
        for (auto i: nums) {
           if (i & sumxor) ans1 ^= i;
           else ans2 ^= i;
        }
        return vector<int>{ans1, ans2};
    }
};