一、题目原型：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素
二、题目意思剖析：
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 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
}
第二种：异或法
找到数组里唯一不同的那个数字，其实可以用异或法。
两个相同数字 异或所得到的是0，可以测试下。
{
var temp: Int = 2
temp ^= 2
print(temp)
}
打印的temp = 0
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。
个人博客地址
