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;
    }
};

LeetCode-260 Single Number III