算法练习第九天——只出现一次的数字

算法练习第九天——只出现一次的数字

只出现一次的数字题目

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

示例一：

输入: [3,3,5] 输出: 5

示例二：

输入: [5,6,2,6,2] 输出: 5

示例三：

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

示例四：

输入: [0,10,2,10,2] 输出: 0

解题思路

方法一：哈希表

我们可以从题目入手，既然给定的数组为非空，并且除了一个元素其余元素都出现了两次，说明数组也不止一个元素，那我们可以创建一个哈希表，然后通过数字设置为键去累加值，在数组遍历结束后再对哈希表进行遍历寻找值为1的键，就是我们要输出的答案。

func singleNumber(nums []int) int {
    a:=map[int]int{}
    var b int
    for _,j := range nums{
        a[j]++
    }
    for i,j := range a{
        if j == 1{
            b = i
        }
    }
    return b
}

方法二：位运算

按位异或操作符的性质我们可以发现一个按位异或操作的性质：一个值和0进行按位异或操作所得为该值，相同的两个值进行异或操作，所得为0，根据这个性质，由于每个重复元素重复两次，故他们在遍历后将相互抵消，而唯一元素只出现一次，故将得到保留

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

该解法复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。

• 空间复杂度：O(1)。