1.1. 题目
1.1.1. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
1.1.2. 题解:
- 除了一个数是单独一次之外,其他的数最多只会出现两次
- 数字的顺序不一定
1.1.3. 思路:
- 按照说明的要求,我并没有做出来,因为我还是用了 map 存了一下数据,还是使用了额外的空间, 就是把数字出现的次数放入到map里,key是数字,value是出现的次数
- 另外,如果可以存map,而且数字最多只会出现两次,所以 如果该数字出现了两次,其实就可以把这个数字给删了,这样map最后只会有一个值,就是单独出现的那个,这样减少查询次数了
- 看了官方题解,发现最优解就是 数学方法的 异或 了! 大学的离散数学里的基本知识点都忘光咯..
- a ⊕ b ⊕ a = (a ⊕ a) ⊕ b,所以直接把所以的数 进行异或 就可以得到结果了
1.1.4. 代码:
点击显示
func singleNumber(nums []int) int {
numLen := len(nums)
var res int
for i:=0;i<numLen;i++ {
res = res ^ nums[i]
}
return res
}
func singleNumber2(nums []int) int {
if len(nums) == 0 {
return 0
}
numsMap := make(map[int]int)
for i:=0;i<len(nums);i++ {
if numsMap[nums[i]] == 0 {
numsMap[nums[i]] = 1
} else {
numsMap[nums[i]]++
}
}
for k,v := range numsMap {
if v == 1 {
return k
}
}
return 0
}