Find number which appears odd times

給定一個 n 個數的數組，找出指出一次的數字

馬上想到暴力法是一個一個搜索，這樣的時間複雜度是 O(n^2)，顯然不行

稍微好一點的方法是用 Hashmap，key 是每個數字，Value 是 count，這樣可以 O(n) 時間內完成

但是用 hashmap會耗費額外的 O(n/2) 空間

還有沒有更好的方法？

有的，可以用 XOR， XOR有個特性是自己跟自己 XOR的結果是「否」，

也就是把全部的數字XOR起來就會是那個只出現一次的數字，這樣的時間複雜度是 O(n)，沒有額外的空間消耗