漫画：神奇的找出只出现一次的数字！

01

题目分析

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

说明：

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

示例 1:

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

示例 2:

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

我们拿到题目的一瞬间，用脚趾头都能想到可以通过hash表进行暴力求解。因为题目中已经告知我们除了目标元素之外，其他元素都只出现两次。所以我们可以用一个很简单的逻辑“如果出现第一次就放入map中，如果出现第二次就将其删除”，最终map中剩下的唯一一个元素，就是我们要找的目标元素。该种解法过于简单，直接上代码：

func singleNumber(nums []int) int {
    m := make(map[int]int)
    for _, v := range nums {
        if _, exist := m[v]; exist {
            //如果元素存在就删除
            delete(m, v)
        } else {
            //如果不存在将其放入，值随意
            m[v] = 1
        }
    }
    for k, _ := range m {
        return k
    }
    //在当前题目限制条件下，这一行应该是跑不到的
    return 0
}

但是很明显，这种解法并不是我们想要的。因为这种情况下，我们使用到了额外空间。那我们如何在不使用额外空间的前提下，来完成这道题目呢，下面是我们的思考过程。

02

题目图解

首先我们回忆一下，我们知道的按位异或(xor)运算。（这是专门给基础薄弱的道友准备的，懂的可以自行跳过....）

异或（xor）是一个数学运算符，它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。在异或中，如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。（其实很好记忆，就是男的和女的才能生出孩子，如果两个男的或两个女的，那就不行...）

而异或运算，满足于交换律其实也很好理解，男的和女的，女的和男的，其实都可以生出孩子..

注意：这里需要强调的是，异或属于二进制运算。因为真的有人可能会问我"你说a,b不同则结果为1,那为啥我在编译器里计算3^1,最终结果却是2"这样的问题。

在上面的知识基础上，我们只需要将所有数字按照顺序做异或运算，最终剩下的数字就是唯一的数字。

因为任意两个相同的数字进行异或，结果为0

a ^ a = 0

而0和任意数字进行异或，又等于其本身。比如 10 ^ 0 ,如图：

03

Go语言示例

分析完毕，则代码自成：

func singleNumber(nums []int) int {
    res := 0
    for _, v := range nums {
        res ^= v
    }
    return res
}

注：本系列所有教程中都不会用到复杂的语言特性，大家不需要担心没有学过go。算法思想最重要，使用go纯属本人爱好。同时，本系列所有代码均在leetcode上进行过测试运行，保证其严谨性！