Epoch

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

Note:

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

題意

給一些數字，除了一個數字外，每個數字皆出現兩次，找出只出現一次的數字

想法

設一個table，把value當作index，但不知道數字範圍，若是負數或很大的數，就不好控制。

設一個array，把出現的數字放進去，愈到下一個數字若是曾出現過就紀錄，找出只出現一次的，但 timelimit。

參考網路上強者的作法，竟然用 XOR一行就解決了，原理是

XOR可以找出兩樹不同的地方，相同兩數XOR會得到0，打到這裡想到數學的重要性

在離散提過的交換群，滿足其元素的運算不依賴於他們的次序的群，也就是說

1 ^ 2 ^ 5 ^ 2 ^ 1 = 1 ^ 1 ^ 2 ^ 2 ^ 5 = 0 ^ 0 ^ 5 = 5

大概可以想成這樣，還有好多要學的啊orz