Single Number III(LintCode)

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 这个公式当然是这个比较快。。

 public class Solution {

     /**

      * @param A : An integer array

      * @return : Two integers

      */

     public List<Integer> singleNumberIII(int[] A) {

         List<Integer> list = new ArrayList<Integer>();

         int x = 0;

         for(int a : A) {

             x = x ^ a;

         }

         int lowbit = x & (-x);

         int a = 0;

         int b = 0;

         for(int y : A) {

             if((y & lowbit) == 0) {

                 a = a ^ y;

             }else {

                 b = b ^ y;

             }

         }

         list.add(a);

         list.add(b);

         return list;

     }

 }