LeetCode，只出现一次的数字

力扣题目：

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

说明：

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

• 来源：力扣（LeetCode）
• 链接：https://leetcode-cn.com/problems/single-number

解题思路

1. 暴力破解

• 遍历一次数组，使用哈希表来存储数组中每个元素出现的次数；
• 然后再遍历这个哈希表，找到只出现一次的数字

func singleNumber(nums []int) int {
    l := len(nums)
    var re int
    maps := make(map[int]int)
    for i:=0;i<l;i++ {
        maps[nums[i]]++
    }
    for k,v:=range maps{
        if v == 1{
            re = k
            break
        }
    }
    return re
}

题目要求不使用额外空间，上面我们使用了一个额外的哈希表，所以不符合题目要求。

1. 位运算 对于这道题，我们还可以使用异或运算 ⊕。异或运算有以下三个性质。

• 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
• 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
• 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

因为给定的题目指定，确保是一个非空的数组，且有一个出现一次的元素，其余都会出现两次。使用异或运算，我们将所有元素做异或操作，这样相同的元素会消去，最后剩下独一无二的那个元素。使用异或代码非常简洁，如下：

func singleNumber(nums []int) int {
    for i:=1;i<len(nums);i++ {
        nums[0] ^= nums[i]
    }
    return nums[0]
}

解题中，我们没有使用额外的空间，只使用了题目所提供的数组空间，所以空间复杂度为 O(1)。