一、題目原型：

給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素

二、題目意思剖析：

說(shuō)明：
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來(lái)實(shí)現(xiàn)嗎？
示例 1:
輸入: [2,2,1]
輸出: 1

示例 2:
輸入: [4,1,2,1,2]
輸出: 4

三、解題思路：

第一種

根據(jù)題目意思，數(shù)組的個(gè)數(shù)一定是奇數(shù)。(2+2+2+1+2)類(lèi)似這樣,先排個(gè)序，然后 i = i + 2，一旦前后不同，就return前面那個(gè)數(shù)字。

func singleNumber(_ nums: [Int]) -> Int {
    
    if nums.count == 1 {
        return nums.first!
    }
    
    // 0 0 1 1 2 3 3
    // 除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次 
    // 說(shuō)明數(shù)組個(gè)數(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ù)組里唯一不同的那個(gè)數(shù)字，其實(shí)可以用異或法。
兩個(gè)相同數(shù)字 異或所得到的是0，可以測(cè)試下。

{
    var temp: Int = 2
    temp ^= 2
    print(temp)
}
打印的temp = 0

0異或任何數(shù)字，都等于原數(shù)字本身

{
    var temp: Int = 0
    temp ^= 2
    print(temp)
}
打印的temp = 2

原理：

假設(shè)如果 A = 60，且 B = 13，現(xiàn)在以二進(jì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

& 兩者同時(shí)為真才為真；| 兩者一者為真就為真；^相同為假，不同為真

所以，我們只要用0去異或數(shù)組里所有的數(shù)字，最后得到的就是不同的那個(gè)數(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é)

第一種方法耗時(shí) 144ms，超過(guò)19.02%提交記錄。
第二種方法耗時(shí) 32ms，超過(guò)68.1%提交記錄。
總提交數(shù)：16。
個(gè)人博客地址