Golang面试考题记录 ━━ 只出现一次的数字，学习异或^=处理

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

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

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

方法一：执行82.17%，内存0%完败
用了两次循环，且用了map

func singleNumber1(nums []int) int {
	temp := make(map[int]int, len(nums))
	for _, v := range nums {
		temp[v]  
	}
	for i, v := range temp {
		if v == 1 {
			return i
		}
	}
	return 0
}

方法二：执行0.00%完败，内存100%
嵌套循环，执行速度最慢

func singleNumber2(nums []int) int {
	for i, v := range nums {
		r := 0
		for j, y := range nums {
			if i != j && v == y {
				r  
			}
		}
		if r == 0 {
			return v
		}
	}
	return nums[len(nums)-1]
}

方法三：执行82.27%完败，内存64.85%||100.00%
使用了异或的方法，性价比最高，但是，但是，但是，仅仅适用于本题，后面详解。

func singleNumber3(nums []int) int {
	c := 0
	for _, v := range nums {
		c ^= v //c = c ^ v
	}
	return c
}

参考：leetcode go语言 刷题 只出现一次的数字

只有一个出现一次，其他元素均出现两次，那么数组长度肯定是奇数，只要先排序在两两比较就可以找到出现一次的数字了。
但是题目提出了要求：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
这个要求就增加了难度，似乎进入了死胡同。这时候就要想到一些黑魔法，例如异或。
异或（^）【同0异1】
运算规则：0^0=0；01=1；1^0=1；11=0；
用途：
（1）使特定位翻转，异或上一个要翻转位数为1，其余位为0的数值即可。
例：设x=11101100，将x的低四位翻转。令x^00001111=11100011
（2）与0异或，保留原值。
（3）基于异或运算，不引用新变量，交换两个变量的值
可以发现相同的数字进行异或那么得到的值为0，任何数字同0异或得到的都是其本身。
所以这道题用异或就可以了。

举个具体的例子

v := 0  //1、 0的二进制：0
v ^= 32 //2、32的二进制：0100000，异或后得值：0100000（32）
v ^= 64 //3、64的二进制：1000000，异或后得值：1100000（96）
v ^= 5  //4、 5的二进制：0000101，异或后得值：1100101（101）
v ^= 15 //5、15的二进制：0001111，异或后得值：1101010（106）
v ^= 64 //6、64的二进制：1000000，异或后得值：0101010（42）
v ^= 32 //7、32的二进制：0100000，异或后得值：0001010（10）
v ^= 15 //8、15的二进制：0001111，异或后得值：0000101（5）
// 此处已经得到正确结果5
v ^= 15 //9、15的二进制：0001111，异或后得值：0001010（10）

注意点：
每一步异或后的值可以看出，必须满足重复的数字是两个，且“只出现一次的数字”只有一个，才会得到正确的结果。

如果其中相同的数字有二个以上或者“只出现一次的数字”有一个以上，则结果大相径庭，可能出现不在原数组中的数字。

实际运用需谨慎。