Single Number III

Given 2*n + 2 numbers, every numbers occurs twice except two, find them.

Example

Given [1,2,2,3,4,4,5,3] return 1 and 5

Challenge

O(n) time, O(1) extra space.

 

 

可耻的百度了。。

还是好理解的。当然不一定要用最低位的1，任意找一个1即可。不过有lowbit = xor & -xor 这个公式当然是这个比较快。。

1 public class Solution { 2     /** 3      * @param A : An integer array 4      * @return : Two integers 5      */ 6     public List
        
          singleNumberIII(int[] A) { 7         List
         
           list = new ArrayList
          
           (); 8          9         int x = 0;10         for(int a : A) {11             x = x ^ a;12         }13         int lowbit = x & (-x);14         int a = 0;15         int b = 0;16         for(int y : A) {17             if((y & lowbit) == 0) {18                 a = a ^ y;19             }else {20                 b = b ^ y;21             }22         }23         24         25         list.add(a);26         list.add(b);27         return list;28     }29 }