136. Single Number
136. Single Number
只有一个数字出现一次，其余都两次
一个数和自己异或为0
时间复杂度：O(n)
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
for i in nums:
res = res ^ i
return res
-
Single Number II
137. Single Number II
都出现3次，有一个数出现1次
用one，two，three记录出现1，2，3次的
先更新two，再更新one，更新one & two，更新one，two
时间复杂度：O(n)
代码如下：
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
one = two = three = 0
for i in nums:
two = two | (one & i)
one = one ^ i
three = two & one
one = one & ~three
two = two & ~three
return one
