從 Codility 來看邏輯運算子 — XOR
Jul 4, 2021
最近在刷 Codility 的時候，碰到一個題目是，給定一個 Array 裡面包含 K 的元素的數字，其中必定兩兩成對，只會有一個落單的數字，請寫出一個方法如下定義，當傳入 Array 時，可以得到落單的數字。
func FindOddOccurrencesInArray(A []int) int原本的思維邏輯是使用兩組 Map，for loop 跑完陣列的內容物的時候，並且依照是否有出現過來做判斷，整體的 pseudo code 如下
var evenTimesMap map
var oddTimesMap mapfor element in A {
if evenTimesMap[element] {
continue
}
if oddTimesMap[element] {
oddTimesMap.remove(element)
evenTimesMap[element] = 1
} else {
oddTimesMap[element] = 1
}
}var key = oddTimesMap.Keys.First()
return oddTimesMap[key]
但這樣子的寫法並不好，不止效率不佳，使用到的記憶體也尚未經過最佳化，甚至在執行上也有機率性的出現 Index Out Of Range 的錯誤，因此就思考了一下有沒有更好的解法。
XOR 登場
XOR 是一個數學運算子，表示符號為 ^，其運算邏輯可以想成兩者運算，假設兩者相同則其值為0，若不同則為1，透過實際案例來看
1. a ^ a = 0 // 兩者相同
2. a ^ b = b ^ a // 順序不影響結果
3. a ^ b ^ a = b // 因為 a ^ a = 0, 所以 0 ^ b = b了解 XOR 之後，再把這個運算子帶回題目來看，其實有一個很快的解決方式，就是直接將 Array 中的元素，使用 XOR 運算子串在一起，然後利用相同為 0 的結果，運算到最後的值就會是落單的數字，依照此概念可寫出如下程式碼
var xorElement int
for element in A {
xorElement ^= element
}return xorElement
這樣的運算結果，時間複雜度為 O(N)，但是在空間的時候上卻只有 O(1)，因為其並沒有因為 Array 中元素的數量，來變動其所使用到的記憶體位置大小。
