leetcode-260：只出现一次的数字-iii

题目描述

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案

方法一：位运算

解题思路

• 数组中有两个元素出现了一次。其余元素都出现了两次，将全部元素进行异或操作，最终结果是只出现了一次的两个数字的异或结果
• 该结果为1的位上说明res1和res2不相同
• 相反数相与得到一个只有为1的位上不同（相反数相与得到该数最低位），其余位上均为0的数，以此为依据将数组分为两部分
• 第一部分是和该数相与为0的，第二部分是与该数相与为1的。
• 因为res1和res2在该位上值不同，所以与该数相与，会将res1和res2分到两个部分
• 然后将两部分分别异或，两部分中其余相同的元素都会被抵消，只剩下res1和res2

代码实现

func singleNumber(nums []int) []int {
	diff := 0
	for _, v := range nums {
		diff ^=  v
	}

	div := diff & (-diff)
	res := make([]int, 2)
	for _, v := range nums {
		if v&div == 0 {
			res[0] ^= v
		} else {
			res[1] ^= v
		}
	}
	return res
}

方法二：hash法

解题思路

• 将全部元素存到map中，统计每个元素出现次数
• 遍历map，出现一次的就是res1和res2

代码实现

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