目標：
這題主要目的在於透過題目來介紹前面提過的Bitwise Operation的應用。

原題：

Question:
Given a non-empty 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?

Example 1:
Input: [2,2,1]
Output: 1

Example 2:
Input: [4,1,2,1,2]
Output: 4

分析/解題：
給定一個非空的整數陣列，當中每個元素都出現兩次，
只有一個出現一次而已，題目要求找出那個單獨的數字。

在進一步往BST之前，先來一個簡單但一般不會想到的問題。
這題如果我們以暴力法來解的話，假設不用任何額外的資料結構，
我們可以每拿一個數字就對整個陣列做比較，直到找到沒有重複的數字為止。
但這樣除了時間複雜度會是O(N)以外
(對單一數字，所以每個數字都做完就是O(N^2))，
最後會發現有可能會有拿到先前拿過一次的數字，所以顯然是不太行的。

那輔以資料結構呢？
比較常用的方法是使用HashMap(Python則用dict)，為每個數字計數，
計數完以後就掃過整個對應，看誰只有被數到一次，就是我們要的答案了。
這個方法要先走訪過一遍陣列，再走訪一遍HashMap或dict，
時間/空間複雜度均為O(N)，但還是稍嫌慢了一些。

那有沒有更厲害的解法呢？有！
要了解這個解法怎麼操作，首先我們需要複習一下Bitwise Operation。
當中的XOR的內容是：將兩個數的每個位元兩兩相對，
一個0一個1的時候，結果會是1，否則結果會是0。
這可以讓數字運算得到一些神奇的特性，第一個特性是：

a XOR a = 0

我們拿11=1011(二進位)來試試看：

11        = 1011
11        = 1011
11 XOR 11 = 0000 = 0

因為每一位數都相同，XOR後每一位就都會是0。
第二個特性是：

0 XOR a = a, a XOR 0 = a

因為一邊都是0，所以那個位數是0或1，端看原先a的位元。
再來其他一些重要的特性是：

a XOR b = b XOR a (交換律)

(因每個位元的結果端看該位元總共有奇數或偶數個1，和順序無關)

(a XOR b) XOR c = a XOR (b XOR c) = a XOR (c XOR b) = a XOR c XOR b

(不論哪邊先做，結果都是看有奇數個1->結果是1，偶數個1->結果是0)
(最前面的部分是標準的結合律)

推而廣之，我們可以得到XOR具有交換律和結合律。
將它的運算的數字左右調換，或者哪個先做，哪個後做，均不影響結果。

回到問題來，假設我們目標的答案是r，
那麼將陣列中所有的數字XOR起來，會發生什麼事情呢？
我們根據前面的已知，將陣列自己調換一下，應該可以變成：
r XOR a XOR a XOR b XOR b XOR c XOR c ……的形式。
(因為怎麼換都不應該影響結果)

於是，陣列全部XOR的結果會等於r XOR 0 XOR 0 XOR…… = r
(其它的兩兩XOR後會變0)

也就是說，將每個數都進行XOR後，結果會留存下那個唯一單獨的數字。
寫成程式碼如下，宣告變數為0後從index 0開始，
或直接將陣列的第一個數指派給它並從index 1開始，
實測上沒有特別感受到時間差異，讀者依照自己的喜好和習慣嘗試即可。

Java的部分用了語法蜜糖，
int e:nums代表自nums陣列按順序每次拿一個數並交給e。

Java:

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int e:nums) single ^= e;
        return single;
    }
}

Python:

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = nums[0]
        for i in range(1, len(nums)):
            res ^= nums[i]
        return res

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(由於只要整個陣列掃過一次就結束了且無須額外的陣列空間，
時間複雜度為O(N)，空間複雜度則為O(1))

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0098. Validate Binary Search Tree (Medium)