剑指offer-数组中只出现一次的数字

一、题意

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

二、思路

• 题目一直在强调一个(或两个)数字只出现一次，其他的出现两次。可以联想到异或运算。异或的一个性质是：任何一个数字异或它自己都等于0。如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字。

• 那么如何在一个数组中找到两个只出现一次的数字呢？如果可以将原始数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，而其他数字都成对出现。就可以用上述方法找到出现一次的数字。

• 从头到尾一次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数组的异或结果。因为其他数字都出现了两次，在异或中全部抵消了。由于两个数字肯定不一样，那么异或的结果肯定不为0，也就是说这个结果数组的二进制表示至少有一个位为1。我们在结果数组中找到第一个为1的位的位置，记为第n位。现在我们以第n位是不是1为标准把元数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0。

三、代码实现

package main

import "fmt"

func oneNumber(nums []int) []int {
	xor := 0
	// 遍历数组进行异或操作
	for _, v := range nums {
		xor ^= v
	}

	// 取xor从右往左第一位为1的位
	// 与自身的负数相与
	// 负数的补码：符号位为1，其余位为该数绝对值的原码按位取反，然后再加1
	// 2=0010 -2=1101+1=1110 0010&1110=0010
	// 用来判断xor是不是2的N次方
	lowbit := xor & -xor

	one, two := 0, 0
	for _, v := range nums{
		if lowbit&v == 0 {
			one ^= v
		} else {
			two ^= v
		}
	}
	return []int{one, two}
}

func main() {
	test := []int{2, 4, 3, 6, 3, 2, 5, 5}
	result := oneNumber(test)
	fmt.Print(result)
}

// 输出如下：
[4 6]
Process finished with exit code 0