[算法] 剑指offer golang 面试题40：数组中只出现一次的数字

[算法] 剑指offer golang 面试题40：数组中只出现一次的数字 题目1: 其他元素会出现2次

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

思路1: 亦或

异或是相同的位为0, 不同的位为1
所以相同的元素最后将会抵消, 最后亦或的值就是返回值.

代码

func singleNumber(nums []int) int {
    resp := 0 
    for i :=0 ; i < len(nums); i++ {
        resp ^= nums[i]
    }
    return resp 
}

题目2: 其他元素会出现3次

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4
示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：

1 <= nums.length <= 10000
1 <= nums[i] < 2^31

思路1: 记录二进制位出现次数

如果数字出现3次,那么这个数组的每个二进制位也会出现3次
用一个 bits[32] 记录每个数字的位的二进制的和,如果该和为0或者能被3整除该位就是0,反之该位就是1

代码

func singleNumber(nums []int) int {
	// 参数处理
	if len(nums) == 0 {
		//参数处理
		return 0
	}
	//1. 记录
	bits := make([]int, 32)
	for i := 0; i < len(nums); i++ {
		for j := 0; j < 32; j++ {
			if nums[i]&(1<<j) != 0 {
				bits[j]++
			}
		}
	}
	//2.计算最后的值
	resp := 0
	for k := 0; k < 32; k++ {
		if bits[k]%3 == 1 {
			//将该位设置为1
			resp |= (1 << k)
		}
	}
	return resp
}

题目3: 有2个只出现一次的数字, 其他的数字出现2次

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O（n），空间复杂度是O（1）。例如输入数组{2,4,3,6,3,2,5,5}，因为只有4、6这两个数字只出现一次，其他数字都出现了两次，所以输出4和6。

思路 最后的异或结果不为0, 找到一个不为0的位以这个不为0的位为分界线将这个位为0的和不为0的分为2组(这样2个只出现一次的数字一定会分到2个组里面)这2个组再异或分别得到结果