Problem

Given an array of numbers, where all numbers appear twice except for two numbers that appear only once. Find these two numbers. Try to achieve O(1) space complexity.

Analysis

Although the solution requires O(1) space complexity, this approach is quite complex and difficult to conceive, and it’s challenging to write an algorithm with a small constant factor. Feel the magic of XOR The link above provides the standard approach for this problem. In this method, first XOR all the numbers, and the result will be the XOR of the two numbers that appear only once. Each bit 1 in this result indicates which bits differ between these two numbers. Pick any one of these bits, and divide the array into two groups based on this bit: one group where this bit is 1, and another where this bit is 0. Then, XORing each group separately will give the two numbers we’re looking for.

This leverages the properties of XOR:

a ^ b ^ c = a ^ c ^ b a ^ a = 0 0 ^ a = a a ^ b = c => a ^ c = b

Runtime: 13ms, beats 68% of submissions.

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int axorb = 0, last = 0;
        vector<int> ret(2, 0);
        
        for(auto it = nums.begin(); it!=nums.end() ; it++)
        {
            axorb ^= *it;
        }
        
        last = axorb & (~(axorb - 1));
        
        for(auto it = nums.begin(); it!=nums.end() ; it++)
        {
            if ((last & *it) != 0)
                ret[0] ^= *it;
        }
        
        ret[1] = axorb ^ ret[0];
        
        return ret;
    }
};

Alternative Method

If we’re not restricted to constant space complexity, we can also use a hash table. This approach has good extensibility and is less obscure.

Runtime: 16ms, beats 34% of submissions.

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_set<int> buff(nums.size());
        for(auto i = nums.begin(); i!=nums.end() ; i++)
        {
            auto it = buff.find(*i);
            if(it == buff.end()){
                buff.insert(*i);
            }
            else{
                buff.erase(it);
            }
        }
        vector<int> ret;
        for(const int & i : buff){
            ret.push_back(i);
        }
        return ret;
    }
};