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.reibang.com/p/135a33546f45)是有序序列,更復(fù)雜.
(看討論的)用異或(XOR,或記為⊕)
以下結(jié)論很吊很有用:
0 ⊕ A = A //A為任意數(shù)
A ⊕ A = 0
即,任意數(shù)與0相與都等于其自身,任意數(shù)與其自身異或都為0
補(bǔ)充:
(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) //結(jié)合律
(A ⊕ B) ⊕ (C ⊕ D) = A ⊕ B ⊕ C ⊕ D //可以去掉括號(hào)
A ⊕ B ⊕ C ⊕ D = A ⊕ C ⊕ B ⊕ D //可以隨意交換
即,只要參與異或運(yùn)算的成員不變,任意交換異或順序,結(jié)果都一樣
之前在(http://www.reibang.com/p/99d87c778b24)推導(dǎo)過(guò)的結(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號(hào)存儲(chǔ)異或結(jié)果,節(jié)省空間
}
return nums[0];
}
