给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?
func singleNumber(nums []int) int {
l := len(nums)
var re int
maps := make(map[int]int)
for i:=0;i<l;i++ {
maps[nums[i]]++
}
for k,v:=range maps{
if v == 1{
re = k
break
}
}
return re
}
题目要求不使用额外空间,上面我们使用了一个额外的哈希表,所以不符合题目要求。
因为给定的题目指定,确保是一个非空的数组,且有一个出现一次的元素,其余都会出现两次。使用异或运算,我们将所有元素做异或操作,这样相同的元素会消去,最后剩下独一无二的那个元素。使用异或代码非常简洁,如下:
func singleNumber(nums []int) int {
for i:=1;i<len(nums);i++ {
nums[0] ^= nums[i]
}
return nums[0]
}
解题中,我们没有使用额外的空间,只使用了题目所提供的数组空间,所以空间复杂度为 O(1)。