剑指offer 040、数组中只出现一次的两个数字

题目

题解

哇这道题根本没有想起来会用 异或 来解决的

力扣的官方解析

思路

算法

• 先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
• 在异或结果中找到任意为 11 的位。
• 根据这一位对所有的数字进行分组。
• 在每个组内进行异或操作，得到两个数字。

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        vector<int> result;
        int res1 = 0, res2 = 0;
        int orSum = 0;
        for (auto x : array) {
            orSum ^= x;
        }
        
        int t = 1;    // 找出异或 结果中哪一位是1
        while ((orSum & t) == 0) {
            t = t << 1;
        }
        for (auto x : array) {
            if (t & x) {
                res1 ^= x;
            }
            else {
                res2 ^= x;
            }
        }
        result.push_back(min(res1, res2));
        result.push_back(max(res1, res2));
        return result;
    }
};