136. 只出现一次的数字

一、题目原型：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素

二、题目意思剖析：

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1

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

三、解题思路：

第一种

根据题目意思，数组的个数一定是奇数。(2+2+2+1+2)类似这样,先排个序，然后 i = i + 2，一旦前后不同，就return前面那个数字。

func singleNumber(_ nums: [Int]) -> Int {
    
    if nums.count == 1 {
        return nums.first!
    }
    
    // 0 0 1 1 2 3 3
    // 除了某个元素只出现一次以外，其余每个元素均出现两次 
    // 说明数组个数一定是奇数
    var mutnums = nums.sorted()
    var index: Int = 0
    while index < mutnums.count {
        //print(index)
        if index+1 >= mutnums.count {
            return mutnums[index]
        }
        //上面代码已经屏蔽掉了index+1越界的情况
        if mutnums[index] != mutnums[index+1] {
            return mutnums[index]
        }
        index = index + 2
    }
    //print(mutnums)
    return -1
}

第二种：异或法

找到数组里唯一不同的那个数字，其实可以用

1	两个相同数字异或所得到的是0，可以测试下。

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

1	0异或任何数字，都等于原数字本身

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


######原理：
假设如果 A = 60，且 B = 13，现在以二进制格式表示，它们如下所示：

A = 0011 1100
B = 0000 1101

A&B = 0000 1100

A|B = 0011 1101

A^B = 0011 0001

~A  = 1100 0011

>& 两者同时为真才为真；| 两者一者为真就为真；^相同为假，不同为真

所以，我们只要用0去异或数组里所有的数字，最后得到的就是不同的那个数字。

func singleNumber(_ nums: [Int]) -> Int {
if nums.count == 1 {
return nums.first!
}
// 异或
var temp: Int = 0
for num in nums {
temp ^= num
}
return temp
}
`

四、小结

第一种方法耗时 144ms，超过19.02%提交记录。
第二种方法耗时 32ms，超过68.1%提交记录。
总提交数：16。