Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

得出数组异或的结果，根据这个结果中某一位的1，将数组分成两部分，那么要求的两个数就分别在这两部分中。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res(2, 0);
        int xor_res = 0;
        for(int i = 0; i < nums.size(); i++)
            xor_res ^= nums[i];

        int pos = 0;
        for(int i = 0; i < 32; i++){
            if(xor_res & (1<<i)){
                pos = i;
                break;
            }
        }

        for(auto num:nums){
            if(num&(1<<pos))
                res[0] ^= num;
            else
                res[1] ^= num;
        }

        return res;
    }
};

class Solution
{
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        // Pass 1 : 
        // Get the XOR of the two numbers we need to find
        int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        // Get its last set bit得到bit位上为1的最后一位
        diff &= -diff;

        // Pass 2 :
        vector<int> rets = {0, 0}; // this vector stores the two numbers we will return
        for (int num : nums)
        {
            if ((num & diff) == 0) // the bit is not set
            {
                rets[0] ^= num;
            }
            else // the bit is set
            {
                rets[1] ^= num;
            }
        }
        return rets;
    }
};