260. 只出现一次的数字 III

260. 只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]
注意：

结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

• 分析
  这道题的解法是用mask分开两个数，因为xor的结果为1，则同一位上两个数，必定一个为0一个为1，这样用一个mask再做xor,判断结果就可分开两个数，解法参考 Leetcode 260：只出现一次的数字 III（最详细的解法！！！)
• code

package main
import "fmt"
func singleNumber(nums []int) []int {
	single:=0
	for _,j:=range nums{
		single^=j
	}
	mask:=single&-single //选取mask,因为异或所以a,b中一定有一个在该位是1，另一个是0
	var res [2]int
	for _,j:=range nums{
		if mask&j==mask{ //但其他数据也可能和mask相同，但因为偶数次，被异或消除了
			res[0]^=j    //最终，偶数次的在mask和非mask下都被消了，只剩下a,b 即为所求，且分开
		}else{
			res[1]^=j
		}
	}
	return res[:]
}
/*
期考如果
k个single(k>2),但是可能得到的xor是0，那么久无法进行mask,因为xor为0，k个数在该同一位上，可能是偶数个1，也可能是全0
但k=2是，xor为1，只有0，1这种可能
k>2,该方法就不奏效了
*/
func main(){
	fmt.Println(singleNumber([]int{1,2,1,3,2,5}))
}

• 解法参考 Leetcode 260：只出现一次的数字 III（最详细的解法！！！)

最后

以上就是迷人宝马为你收集整理的260. 只出现一次的数字 III的全部内容，希望文章能够帮你解决260. 只出现一次的数字 III所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。