題目
給定一個(gè)非空整數(shù)數(shù)組涩搓，除了某個(gè)元素只出現(xiàn)一次以外污秆，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素昧甘。
可以不使用額外空間來實(shí)現(xiàn)嗎良拼？
示例1
輸入: [2,2,1]
輸出: 1
示例2
輸入: [4,1,2,1,2]
輸出: 4
思路
????普通情況下在數(shù)組中找到元素出現(xiàn)次數(shù)，可以通過哈希表存儲(chǔ)每個(gè)元素和該元素出現(xiàn)的次數(shù)充边。遍歷數(shù)組即可得到每個(gè)元素出現(xiàn)的次數(shù)庸推，并更新哈希表，最后遍歷哈希表痛黎，得到只出現(xiàn)一次的元素予弧。
????數(shù)組中 個(gè)元素均出現(xiàn)兩次，也可以使用集合存儲(chǔ)出現(xiàn)過的元素湖饱，第一次出現(xiàn)加入集合掖蛤，第二次出現(xiàn)從集合中刪除該元素，最終得到集合中唯一的元素井厌。
????這兩種解法都需要使用 的空間蚓庭，那么如何可以不使用額外空間呢？我們可以使用異或運(yùn)算仅仆，異或運(yùn)算的運(yùn)算法則如下：
歸零律：
恒等律：
交換律：
結(jié)合律：
自反：
????數(shù)組中 個(gè)元素重復(fù)器赞，假設(shè)
，則數(shù)組中有 m 個(gè)數(shù)各出現(xiàn)兩次墓拜，一個(gè)數(shù)出現(xiàn)一次港柜。令
為出現(xiàn)兩次的 m 個(gè)數(shù)爽锥，
為出現(xiàn)一次的數(shù)。數(shù)組中的全部元素的異或運(yùn)算結(jié)果總是可以寫成如下形式：
????因此畔柔，將所有數(shù)字按照順序異或運(yùn)算氯夷，最后剩下的結(jié)果即為唯一的數(shù)字 。
代碼實(shí)現(xiàn)
int singleNumber(int* nums, int numsSize){
int ret = 0;
for(int i = 0; i < numsSize;i++){
ret ^= nums[i];
}
return ret;
}
