描述 Description

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?

[Single Number III]

分析 Analysis

方法1

本题是有两个未知数，是 "Single Number" 这道题的扩展，直接做异或不行。有没有办法把两个未知数分开，使得可以应用Single Number 的解法呢？

设x, y是那两个未知数，那么如果对这个数组做异或的话，结果实质上等于x ^ y，因为其他数都出现了两次，被抵消了。

仅仅通过最后异或出来的值，是没办法区分出x和y的，但是足以帮助我们把x和y划分到不停地子数组中去。对于x和y，由于二者不相等，那么二者至少存在一位不相同，如下图所示：

当找到这个k以后，就可以按照第k位是否等于1，将nums数组划分为两个子数组，相同的两个数一定会被分到同一个数组中去（实际是没有真的划分数组，而是将k位为0和为1的不同数异或到数one和数two上），然后把Single Number的算法直接应用到两个子数组上，就可以求出x和y了（即最后分开异或的结果数one和数two）。

代码 Code

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