260. Single Number III

https://leetcode.com/problems/single-number-iii/

Solution:
Do not have any clue for this question with time complexity of O(n) and space complexity of O(1). Thought about bitwise operation, but still cannot figure out how to distinguish two different numbers until searching online. The reference link is listed below.

First step is to obtain the xor of the two different nums, which is trivial; then is the key part: choose one non-zero bit of the xor result as an indicator to separate the initial nums into two groups. Each group should have one of two unique elements. Then it is trivial to find them.

Code:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res(2, 0);
        int t = 0; 
        for(auto a:nums) t ^= a;
        t &= -t; //the most-right non-zero bit;
        for(auto a: nums){
            if(t&a) res[0] ^=a;
            else res[1] ^=a;
        }
        return res;
    }
};

http://www.cnblogs.com/grandyang/p/4741122.html