本文共 1681 字，大约阅读时间需要 5 分钟。

===问：

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

说明：

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

示例 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}

===解：

参考：

只有一个出现一次，其他元素均出现两次，那么数组长度肯定是奇数，只要先排序在两两比较就可以找到出现一次的数字了。

但是题目提出了要求：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

这个要求就增加了难度，似乎进入了死胡同。这时候就要想到一些黑魔法，例如异或。

异或（^）【同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的二进制：0v ^= 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）// 此处已经得到正确结果5v ^= 15 //9、15的二进制：0001111，异或后得值：0001010（10）

注意点：

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

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

实际运用需谨慎。

转载地址：http://gvkpi.baihongyu.com/