260. Single Number III -------------- M

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.

Example:

Input:  [1,2,1,3,2,5]
Output: [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?

A

就是 先全部XOR， 结果 != 0 ， 找到某一位不为0 的。 然后按照这一位来分成2堆。

分别XOR即可。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int totalOR=0;
        for(auto v:nums)
            totalOR ^= v;
        
        // find a mask bit that totalOR is not 0
        int mask = totalOR  - (totalOR & (totalOR-1));
        int a=0, b =0;
        for(auto v:nums){
            if(mask&v)
                a ^= v;
            else
                b ^= v;
        }
        return vector<int>{a,b};
    }
};
 

---------------------同样的思路， 另一种实现

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // 1) get sum of two non-repeating elements, with bit manipulation
        int sum = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        // 2) get first rightmost set-bit and set everything else to zero. this is where the two-numbers start to differ.
        int mask = (sum & -sum);
        // 3) separate the bits into two parts. all duplicate nums will cancel out with XOR operation. 
        int a =0, b = 0;

        for (auto &v: nums) {
            if (v & mask) 

                a ^= num;   // not set.
            else 

                b ^= num;  // bit is set.
        }
        return vector<int>{a,b};
    }
};

Mistakes: