260. 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?

Solution:

Previous similar problem: 136: single number and 137 single number II

As we know we can use bit operator xor to get rid of all elements that appeared twice. 

Similarly here, we xor all the numbers in the array and let's assume the two elements that we want to get is a and b, so xor all elements in nums will give us x= (a ^b) , x must be a non-zero integer,because they are different, so there must be at least one digit 1 in x's binary format.We can use  ~(x-1) & x to get to get the least digit of 1. Eg. 110100 -1 = 110011, ~110011 = 001100, 001100 & 110100= 100. Because x= y+ 2^n and x-1 = y+2^n-1

^y & y=0, 2^n & (~(2^n-1))=2^n. So ~(x-1) & x= 2^n which is the least position of digit 1.So in this digit position, a and b have different digits. Either a has 0 and b has 1 or a has 1 and b has 0.

With this information, we can split the whole nums array to 2 parts, All the numbers that have 0 at this position and all the numbers that have 1 at this position. We know these two group of numbers are just simply some elements that appear exactly two elements and one element appears only once. So we xor these two group of numbers separately , we can get our results.

  public int[] singleNumber(int[] nums) {  
     int a=nums[0];  
     for(int i=1;i<nums.length;i++){  
       a=a^nums[i];  
     }  
     a=(~(a-1))&a;  
     int[] res=new int[2];  
     for(int i=0;i<nums.length;i++){  
       if((nums[i]&a)==0) res[0]=res[0]^nums[i];  
       else res[1]=res[1]^nums[i];  
     }  
     return res;  
   }