题目

题解

我们先来看下异或的性质（数学里异或的符号是 $\oplus$）：

交换律：$p \oplus q = q \oplus p$
结合律：$p \oplus (q \oplus r) = (p \oplus q) \oplus r$
恒等率：$p \oplus 0 = p$
归零率：$p \oplus p = 0$
自反： $p\oplus q\oplus q=p\oplus 0=p\displaystyle p\oplus q\oplus q=p\oplus 0=p$

遍历两遍数组 设两个唯一的数为a和b

  1. 第一次遍将所有的数异或得到结果all_xor，这与a，b异或的结果是一样的。这一步目的是找到all_xor用于后续分组
  2. 通过异或的结果找到从低到高位第一个为1（即a,b第一个不同位）的位置下标diff_bit，按此下标将数组分组。
  3. 第二次遍历所有的数分组异或，a，b会被分到不同的组，其他相同的数会分到一个组。分组异或之后只剩下a和b，返回即可。
  • 时间复杂度: $O(n)$
  • 空间复杂度: $O(1)$
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int all_xor = 0;
        //第一次遍历
        //所有数按位异或的值等于两个不同的数异或
        for(auto n : nums) all_xor ^= n;
        //两个只有一次的数第一个不同的位为i
        //diff_bit只在第i位为1，其他位为0
        int diff_bit = 1;
        while((diff_bit & all_xor) == 0) diff_bit <<= 1;
        int a = 0, b = 0;
        //第二次遍历
        //按diff_bit分组，a和b会分到不同的组
        //其他相同的都会在一个组，就被异或为0了，只剩a和b
        for(auto n : nums){
            if((n & diff_bit) == 0) a ^= n;
            else b ^= n;
        }
        return {a, b};
    }
};