137.只出现一次的数字Ⅱ
2020-03-18 本文已影响0人
haisongzhang
第137题:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。说明:你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?
137.pngSingle Number Ⅱ
- HashMap求解
统计每个元素出现的次数,最终再返回次数为1的元素
//go
func singleNumber(nums []int) int {
m := make(map[int]int, len(nums))
for _, k := range nums {
m[k]++
}
for k, v := range m {
if v == 1 {
return k
}
}
return 0
}
2.数学方式
原理:{a,a,a,b,b,b,c,c,c} 和{a,a,a,b,b,b,c}, 差了两个c 即:3 (a + b + c) - (a + a + a + b + b + b + c) = 2c
也就是说,如果把原数组去重、再乘以3得到的值,刚好就是要找的元素的2倍。
show code:
//python
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return int((sum(set(nums)) * 3 - sum(nums)) / 2)
3.位运算
对于“每个其余元素,均出现了二次”之所以可以使用“异或”进行求解,原因是因为“异或”操作可以让两数相同归 0。那对于其余元素出现三次的,是不是只要可以让其三者相同归 0,就能达到我们的目的呢?
这里先说第一种方法(注意,到这里我们的问题已经转化成了定义一种 a ? a ? a = 0 的运算),观察一下“异或”运算:
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
是不是可以理解为,其实就是二进制的加法,然后砍掉进位呢?
砍掉进位的过程,是不是又可以理解为对 2 进行取模,也就是取余。到了这里,问题已经非常非常明确了。那我们要完成一个 a ? a ? a = 0 的运算,是不是其实就是让其二进制的每一位数都相加,最后再对 3 进行一个取模的过程呢?(一样,如果要定义一个 a ? a ? a ? a = 0 的运算,那就最后对 4 进行取模就可以了)
show code:
//go
func singleNumber(nums []int) int {
number, res := 0, 0
for i := 0; i < 64; i++ {
//初始化每一位1的个数为0
number = 0
for _, k := range nums {
//通过右移i位的方式,计算每一位1的个数
number += (k >> i) & 1
}
//最终将抵消后剩余的1放到对应的位数上
res |= (number) % 3 << i
}
return res
}
我们通过一个number,来记录每一位数出现的次数。