Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

这题是Amazon的经典面试题。最简单的解法是用hashmap，O(n)即可。但是要用额外的存储空间。

或者是维持一个数组，用于存放没有被配对的数。用二分来更新这个数组，如果数组中没有当前数就加入，有就删除。遍历一遍array之后，数组省下来的就是出现次数为奇数的。 O(nlgn)。

用位运算进行计算。太帅了。

 1 public class Solution {
 2     public int singleNumber(int[] A) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         if(A == null || A.length == 0) return 0;
 5         int a = 0;
 6         for(int i = 0; i < A.length; i ++){
 7             a ^= A[i];
 8         }
 9         return a;
10     }
11 }

不过这个只能对只有一个数出现奇数次有效。