Description

给定一个数组$nums[]$，里面有2个数只出现一次，其它数只出现两次，找出前者

Constraints

要求$O(n)$时间复杂度，$O(1)$空间复杂度

Solution

二进制分组。设$sum$为xor之和，$a,b$为答案，由性质可知$sum=a\oplus b$

但是这个时候仍不足以区分答案。进一步发现$sum$里面必然有一个位设为1，以此作为二进制分组

划分为2组后就是低配版Single Number问题

Code

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int sum = 0;
        for(auto n : nums) sum ^= n;
        int pos;
        for(auto p = 31; ~p; --p) {
            if(sum >> p & 1) {
                pos = p;
                break;
            }
        }
        vector<int> ab(2);
        for(auto n : nums) {
            ab[n >> pos & 1] ^= n;
        }
        return ab;
    }
};

Link

LeetCode-260 Single Number III