题解 | 数组中只出现一次的两个数字

核心思路：分组异或

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& nums) {
        // 1. 整体异或，得到两个目标数字的异或值
        int xorResult = 0;
        for (int num : nums) {
            xorResult ^= num;
        }
        
        // 2. 找到异或结果中为1的最低位（两个数字不同的位）
        int mask = 1;
        while ((xorResult & mask) == 0) {
            mask <<= 1;
        }
        
        // 3. 根据mask将数组分成两组，分别异或
        int num1 = 0, num2 = 0;
        for (int num : nums) {
            if (num & mask) {
                num1 ^= num;  // 该位为1的数字
            } else {
                num2 ^= num;  // 该位为0的数字
            }
        }
        
        // 4. 按非降序排列返回
        if (num1 > num2) {
            return {num2, num1};
        }
        return {num1, num2};
    }
};

1. 整体异或：将所有数字进行异或操作，得到的结果就是两个目标数字的异或值
2. 寻找差异位：找到异或结果中为1的某一位，这一位说明两个目标数字在该位上不同
3. 分组：根据这个差异位将数组分成两组，每组包含一个目标数字和若干对相同数字
4. 分别异或：对每组分别进行异或，得到两个目标数字

寻找差异位作用：找到两个目标数字不同的最低位。

原理：

• 两个不同的数字异或，结果为1的位就是它们不同的位
• 我们选择其中一个差异位作为分组依据

分组分别异或作用：将两个目标数字分到不同组，然后分别找出。

原理：

• 根据差异位将数组分成两组
• 每组包含一个目标数字和若干对相同数字
• 相同数字会被分到同一组（因为它们在该位上的值相同）
• 对每组分别异或，相同数字相互抵消，只剩下目标数字