【leetcode】136.只出现一次的数字

leetcode题目

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

说明：

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

思路 1：

我在做这个题的时候，首先是想到了暴力的解法，也就是两层 for 循环，逐一比对，自身与自身不比较，就可以获得答案，我是用 go 写的，代码如下：

func singleNumber(nums []int) int {
    length := len(nums)
    if length == 1 {
        return nums[0]
    }
    
    target := nums[0]
    for i:= 0; i < length; i++ {
        flag := true
        for j := 0; j < length; j++ {
            if i == j {
                continue
            } else if nums[i] == nums[j] {
                flag = false
                break
            }
        }
        if flag {
            target = nums[i]
            return target
        }
    }
    
    return target
}

显然，这并未达到线性时间复杂度，所以肯定有优化的空间，那究竟用什么方法才可以减少时间复杂度呢？

其实根据这个，言下之意，通过某种方法，可以只用一层循环就可以达到目的。随即想了好久后，我得出：

思路 2：

可以通过位运算中的异或运算来做，因为题目说了，只有一个是不同的，其他都是两个相同的数字，用异或，可以让两个相同的数变为 0。

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

好的，提交完成，代码通过。

那么问题来了：

为什么会用到异或呢？异或的本质是什么？

如果拓展到有三个数相同，而不是两个数相同，又该怎么做呢？

欢迎在评论区评论，说说你的想法。