題目來源：Single Number

問題
給予一個 integer 陣列，每一個數字都會出現過兩次，只有一個數字會出現一次，請將那個數字給找出來。
在解此題目時如果可以使用線性的時間複雜度以及不使用額外的記憶體會更好（optional）。

例子
[ 1 3 5 7 9 9 7 5 1 ] -> 答案就是 3 (只出現過一次)
[ 1 3 5 7 9 1 7 9 ] -> 不可能會有這種題目，因為題目說了，只有一個數字會是孤單的，其他**保證**都會出現兩次。

想法
第一次看到這題目時，如果不要使用到額外記憶體，最簡單的方法就是 先排序 在找出沒有伴的 她(他)...
假設題目是 [1 3 5 7 9 1 3 5 7] -> 經由排序後得到 [1 1 3 3 5 5 7 7 9]
接著兩兩相比就可以發現 9 的前後都沒有 9，就可以得知，答案是 9 了。
這個方式的優點是不會使用到 額外的記憶體 , 缺點是在最糟的情況是時間複雜度可能是 O(nLogn) (假設是使用 QuickSort)

後來就發現有一個更快速的方式，既不會用到額外的記憶體，也絕對是線性時間複雜度 O(N)
那就是使用 XOR

常寫程式的人對於 AND 及 OR 或 NOT 一定不陌生，但對於 XOR 可能相對的稍稍陌生了些，但是也一定知道 XOR 這傢伙的存在。因為這是在學習布林運算時的主角之一。

而 XOR 的特色就是 兩兩相同時會抵銷, 舉例來說：
A XOR A XOR B 得到的答案就會是 B
A XOR A XOR B XOR B XOR D XOR C XOR C 得到的答案就是 D
A XOR B XOR A XOR B XOR C 得到的答案就會是 C

他的邏輯就是：

虛擬碼
所以，根據以上的介紹，這題就變得非常簡單了

assign array[0] to result  
for i in array 1st element to array last element  
assign result xor array i into result  
return result  

• 如果你用 C＃ 可以利用我的 測試程式 來驗證
• 如果你用 Java or Python or C++ 可上 LeetCode Online Judge 驗證
• 還是想不出來嗎？參考我的吧！

Java 先排序，在兩兩相比
public int singleNumber(int[] A) {
Arrays.sort(A);

boolean isFirstHit = true;
int result = -1;
for (int i = 0; i < A.length; i++) {
if (isFirstHit) {
result = A[i];
isFirstHit = false;
} else {
if (result == A[i])
isFirstHit = true;
else
break;
}
}

return result;
}

C# 解答 採用 XOR
public static int SolutionXOR(int[] A)
{
int result = A[0];
for (int i = 1; i < A.Length; i++)
{
result = result ^ A[i];
}
return result;
}

Python 解答 採用 XOR
def singleNumber(self, A):
if len(A) == 1:
return A[0]

result = A[0]
for i in range(1, len(A), 1):
result = result ^ A[i]
return result