只出现一次的数字

题目描述

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

示例

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

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

解题思路

自做

通过哈希表存储元素出现的次数，再次遍历数组，找到第一个出现次数为1的元素。

使用这种方法因为要遍历两次数组，所以时间复杂度为O(n)。

// 18ms
func singleNumber(nums []int) int {
    m := make(map[int]bool)
    for _, v := range nums {
        if ok, _ := m[v]; ok {
            m[v] = false
        } else {
            m[v] = true
        }
    }
    for k, v := range m {
        if v {
            return k
        }
    }
    return -1
}

那么有没有一种方法可以只遍历一次数组呢？

学习

通过异或运算，可以实现只遍历一次数组。

异或运算有以下几个特点：

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

因此，对数组中的所有元素进行异或运算，最终结果就是只出现一次的元素。

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

总结

今天刷了一道简单的题目，只出现一次的数字。自己的解法是通过哈希表存储元素出现的次数，再次遍历数组，找到第一个出现次数为1的元素。学习了通过异或运算实现只遍历一次数组。

明天继续刷题，加油！