Given an 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?

思路:這道題不像之前的540. Single Element in a Sorted Array(http://www.itdecent.cn/p/135a33546f45)是有序序列,更復(fù)雜.
(看討論的)用異或(XOR,或記為⊕)
以下結(jié)論很吊很有用:

0 ⊕ A = A //A為任意數(shù)
A ⊕ A = 0
即,任意數(shù)與0相與都等于其自身,任意數(shù)與其自身異或都為0

補充:
(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)  //結(jié)合律
(A ⊕ B) ⊕ (C ⊕ D) = A ⊕ B ⊕ C ⊕ D  //可以去掉括號
A ⊕ B ⊕ C ⊕ D = A ⊕ C ⊕ B ⊕ D  //可以隨意交換
即,只要參與異或運算的成員不變,任意交換異或順序,結(jié)果都一樣

之前在(http://www.itdecent.cn/p/99d87c778b24)推導(dǎo)過的結(jié)論也可以由上述結(jié)論推出:

若f ⊕ m = G,則:
f ⊕ G = m //推導(dǎo): f ⊕ G = f ⊕ (f ⊕ m) = f ⊕ f ⊕ m = 0 ⊕ m = m)
m ⊕ G = f //同上

綜上所述,數(shù)組中若存在重復(fù)兩次的數(shù)i,則其異或結(jié)果必為0.因此遍歷數(shù)組,將所有元素異或,最后剩下的必定是出現(xiàn)單次的數(shù).

int singleNumber(vector<int>& nums) {
    for (int i = 1; i < nums.size(); i++) {  //遍歷數(shù)組
        nums[0] ^= nums[i];  //直接用第0號存儲異或結(jié)果,節(jié)省空間
    }
    return nums[0];
}