题目描述

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

方法一：hash法

解题思路

• 以数组元素为key，将其出现的次数都存到map中
• 遍历map，只出现一次的返回

代码实现

func singleNumber(nums []int) int {
	countMap := make(map[int]int)
	for _, v := range nums {
		count, ok := countMap[v]
		if ok {
			countMap[v] = count+1
		} else {
			countMap[v] = 1
		}
	}

	for k, v := range countMap {
		if v == 1 {
			return k
		}
	}
	return 0
}

方法二：位运算

解题思路

• 求每一位上1出现的次数，对3取余
• 用0与其每一位的结果异或，就是只出现一次的值

代码实现

func singleNumber(nums []int) int {
	res := 0
	for i := 0; i < 64; i++ {
		sum := 0
		for _, v := range nums {
			sum += v >> i & 1
		}
		res ^= (sum%3) << i
	}
	return res
}