LeetCode | Day 7
by CUNOE, April 11, 2024
只出现一次的数字
题目描述
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
示例
输入: [2,2,1]
输出: 1
输入: [4,1,2,1,2]
输出: 4
解题思路
自做
通过哈希表存储元素出现的次数,再次遍历数组,找到第一个出现次数为1的元素。
使用这种方法因为要遍历两次数组,所以时间复杂度为O(n)。
// 18ms
func singleNumber(nums []int) int {
m := make(map[int]bool)
for _, v := range nums {
if ok, _ := m[v]; ok {
m[v] = false
} else {
m[v] = true
}
}
for k, v := range m {
if v {
return k
}
}
return -1
}
那么有没有一种方法可以只遍历一次数组呢?
学习
通过异或运算,可以实现只遍历一次数组。
异或运算有以下几个特点:
- 任何数和 0 做异或运算,结果仍然是原来的数,即 a⊕0=a
- 任何数和其自身做异或运算,结果是 0,即 a⊕a=0
- 异或运算满足交换律和结合律,即 a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
因此,对数组中的所有元素进行异或运算,最终结果就是只出现一次的元素。
func singleNumber(nums []int) int {
single := 0
for _, num := range nums {
single ^= num
}
return single
}
总结
今天刷了一道简单的题目,只出现一次的数字。自己的解法是通过哈希表存储元素出现的次数,再次遍历数组,找到第一个出现次数为1的元素。学习了通过异或运算实现只遍历一次数组。
明天继续刷题,加油!