题目链接: 剑指 Offer 56 - I. 数组中数字出现的次数
题目描述:
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
解法思路:
代码:
func singleNumbers(nums []int) []int {
//1. 采用异或运算的方式
sum := 0
// 所有的数进行异或,最终得到的就是 x^y (x,y 就是那两个只出现一次的数)
for _,v := range nums{
sum ^=v
}
// 由于 x!=y ,说明此时 sum 中一定有一位等于1
//2. 找到 sum 中任意一位1
k := 1
for sum & k == 0 {
k <<= 1
}
//3. 将所有的数划分成两个集合,一个包含x,一个包含y
first := 0
for _,v := range nums{
if v & k == 0 {
first ^= v
}
}
//另一个集合的异或 = 总异或 ^ 前一个集合
second := sum ^ first
return []int{first,second}
}