260. Single Number III

problem 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.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

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

algorithm thought

single number系列的第三题了。这一题是有两个数为异或的情况。这里和前面两题不同。前面两次只需要得到最后一个解。所以用之前的状态分析法也不合适。

对于这题，直接将所有数异或。最后得到的结果肯定是两个数异或的值。这种题还有个窍门就是，如果所有操作都是用的位操作的话，可以直接看做操作单个bit就行。在最后的结果中，找到一个为1的位。xor结果为1，说明一个是1一个是0.然后我们再遍历一遍数组，将所有这个位为1的数异或，所有为0的异或。最后得到的数就是结果。

问题是，如果高效的找到一个bit为1的位呢。将这个数和它的负数相与即可。负数是补码，恰好能得到第一个为1的位。

code

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int a=0,b=0,xorres=0;
        for(int i=0;i<nums.size();++i){
            xorres^=nums[i];
        }
        xorres&=(-xorres);
        for(auto num:nums){
            if(num&xorres){
                a^=num;
            }else{
                b^=num;
            }
        }
        return  {a,b};
    }
};

algorithm analysis

这里一次遍历数组，时间复杂度O(n)