力扣(LeetCode)260. 只出现一次的数字 III(C++)

位运算

请看题目描述：给你一个整数数组nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。根据136. 只出现一次的数字，可知：nums所有数字的异或和x，等于恰好只出现一次的两个元素x1,x2的异或和，$x=x1\oplus x2$。

x等于x1和x2的异或和，首先x1和x2的值不相同，否则这两个元素出现两次，违背题意。x1和x2数值有差异(一个为0，一个为1，异或得1)的数位决定了x的值；且容易找到一个有差异的数位flag=x^-x，flag是x的二进制最低位1的数值。请看关键步骤：根据数位差异，把nums的数值分为两类，则其中一类包含x1；另一类包含x2。

根据数位差异，异或两类，得到答案x1, x2，即为所求。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unsigned int x = 0;
        for (auto &t : nums) {
            x ^= t; // x1 ^ x2;
        }
        int x1 = 0, x2 = 0;
        int flag = x & -x; // x的最低位二进制1的数值
        for (auto &t : nums) {
            if (t & flag) { // t对应flag位是1
                x1 ^= t;
            } else {
                x2 ^= t;
            }
        }
        return {x1, x2};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度 $O(n)$：$n$是$nums$的长度，遍历$nums$的时间复杂度$O(n)$。
空间复杂度 $O(1)$：只使用常数级空间。

致语

• 理解思路很重要。
• 请读者放心留言，可以是疑惑的点，或者感谢/夸奖也可以！！墨染看到会回复的。