2015年11月4日星期三

Leetcode 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 1:Use xor to get the value of num1 XOR num2, find a bit not zero. use this bit to seperate the array into 2 groups (bit=1 and bit=0). So num1 and num2 will be separate. Then do xor to each group to find the num 1 and num 2.
 public class Solution {  
   public int[] singleNumber(int[] nums) {  
     int xor=0;  
     for (int x: nums) xor^=x;  
     int i=0;  
     while ((xor>>i&1)==0) i++;  
     int[] res=new int[2];  
     for (int x: nums) {  
       if ((x>>i&1)==0) res[0]^=x;  
       else res[1]^=x;  
     }  
     return res;  
   }  
 }  

没有评论:

发表评论