一、題目原型：
給定一個非空整數(shù)數(shù)組擅羞，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次义图。找出那個只出現(xiàn)了一次的元素
二、題目意思剖析：
說明：
你的算法應該具有線性時間復雜度召烂。 你可以不使用額外空間來實現(xiàn)嗎碱工？
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
三、解題思路：
第一種
根據(jù)題目意思，數(shù)組的個數(shù)一定是奇數(shù)怕篷。(2+2+2+1+2)類似這樣,先排個序历筝，然后 i = i + 2，一旦前后不同廊谓，就return前面那個數(shù)字梳猪。
func singleNumber(_ nums: [Int]) -> Int {
if nums.count == 1 {
return nums.first!
}
// 0 0 1 1 2 3 3
// 除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次
// 說明數(shù)組個數(shù)一定是奇數(shù)
var mutnums = nums.sorted()
var index: Int = 0
while index < mutnums.count {
//print(index)
if index+1 >= mutnums.count {
return mutnums[index]
}
//上面代碼已經(jīng)屏蔽掉了index+1越界的情況
if mutnums[index] != mutnums[index+1] {
return mutnums[index]
}
index = index + 2
}
//print(mutnums)
return -1
}
第二種：異或法
找到數(shù)組里唯一不同的那個數(shù)字蒸痹，其實可以用異或法春弥。
兩個相同數(shù)字 異或所得到的是0，可以測試下叠荠。
{
var temp: Int = 2
temp ^= 2
print(temp)
}
打印的temp = 0
0異或任何數(shù)字匿沛，都等于原數(shù)字本身
{
var temp: Int = 0
temp ^= 2
print(temp)
}
打印的temp = 2
原理：
假設如果 A = 60，且 B = 13榛鼎，現(xiàn)在以二進制格式表示逃呼，它們?nèi)缦滤荆?/p>
A = 0011 1100
B = 0000 1101
A&B = 0000 1100
A|B = 0011 1101
A^B = 0011 0001
~A = 1100 0011
& 兩者同時為真才為真；| 兩者一者為真就為真者娱；^相同為假抡笼，不同為真
所以，我們只要用0去異或數(shù)組里所有的數(shù)字黄鳍，最后得到的就是不同的那個數(shù)字推姻。
func singleNumber(_ nums: [Int]) -> Int {
if nums.count == 1 {
return nums.first!
}
// 異或
var temp: Int = 0
for num in nums {
temp ^= num
}
return temp
}
四、小結(jié)
第一種方法耗時 144ms际起，超過19.02%提交記錄拾碌。
第二種方法耗時 32ms，超過68.1%提交記錄街望。
總提交數(shù)：16校翔。
個人博客地址
