56.md

数组中只出现一次的两个数字

题目

• 一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字
• 要求：空间复杂度 O(1)，时间复杂度 O(n)
• 提示：输出时按非降序排列

示例

• 输入：[1,4,1,6]
• 返回值：[4,6]
• 说明：返回的结果中较小的数排在前面

思路

实现

func FindNumsAppearOnce(data []int) []int {
	if nil == data || len(data) < 2 {
		return []int{}
	}
	// 先将全部数进行异或运算，得出最终结果
	var result int
	for _, v := range data {
		result ^= v
	}
	// 找到那个可以充当分组去进行与运算的数
	// 从最低位开始找起
	mask := 1
	for result&mask == 0 {
		mask <<= 1
	}
	// 进行分组，分成两组，转换为两组 求出现一次的数字 去求
	var num1, num2 int
	for _, v := range data {
		if v&mask == 0 {
			num1 ^= v
		} else {
			num2 ^= v
		}
	}
	// 输出时按非降序排列
	if num1 > num2 {
		num1, num2 = num2, num1
	}
	return []int{num1, num2}
}