LeetCode刷题DAY 5:只出现一次的数字升级版,进一步深入理解位运算,灵活运用异或、非、与。
1
题目描述
给定一个非空整数数组,只有一个数字出现一次,其余出现三次,找出只出现一次的数字。如输入[3,4,5,4,3,3],输出5。
2
解题
思路一:集合差值
对集合进行切片,生成三个集合,找到与另外两个集合不同的集合缺少的数字。如集合[2,2,3,2],先对集合进行排序,得到[2,2,2,3],通过切片生成集合[2,3]、[2]、[2],比较集合之间元素差别,得到输出结果3。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
nums.sort()
a=len(set(nums[::2]))
b=len(set(nums[1::2]))
if a==b:
return list(set(nums[::3]) - set(nums[2::3]))[0]
else:
return list(set(nums[::3]) - set(nums[1::3]))[0]
思路二:位运算
通过set方法时空复杂度都是O(N),位运算可以使得空间复杂度降为O(1)。在LeetCode刷题DAY 5:只出现一次的数字中使用的“异或”其实就是同一状态出现两次则归零,即0->1->10=0的变化,在本题中则是要让同一状态出现三次归零,即00->01->10->11=00,可见这里需要用两个bit进行状态记录。
这里需要注意的是,要对two、one两位分别计算。对于one,当two=1时,不管输入是什么下一步的one都为0,当two=0时,输入1则one=~one,输入0则one不变。对于two,依赖于one变化后的状态,one新状态为1时,two则为0,one新状态为0时,输入1则two=~two,输入0则不变。因为出现三次就归零,所以one最后保留的是只出现了一次的值。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
one,two = 0,0
for i in nums:
one = one^i & ~two
two = two^i & ~one
return one
当然,对集合进行遍历,通过哈希表记录每个数字出现次数的方法也是可以的,时空复杂度也都是O(N),代码与Day 5思路一一致,此处不再赘述。