medium, bit manipulation
Question
有一個整數(shù)序列垢夹，其中的每個整數(shù)除了一個都出現(xiàn)了3次厢呵，找到那個落單的數(shù)纳鼎。
Notes
Time complexity要求O(n)且不能分配新memory
Solution
使用bit操作來解答. 將所有數(shù)的第i個bit相加建车，再模3的結(jié)果必然是0或者1扩借，因為數(shù)字要么出現(xiàn)3次要么出現(xiàn)1次。然后使用或運算來找到單數(shù)缤至。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ret = 0
for i in xrange(32):
count = 0
for num in nums:
if num>>i & 1:
count+=1
ret |= count%3<<i
if ret >= 2**31:
return ret - 2**32
else:
return ret
另解：使用三個變量
ones -- bitmask表示出現(xiàn)一次的第i個bit
twos -- bitmask表示出現(xiàn)兩次的第i個bit
threes -- bitmask表示出現(xiàn)三次的第i個bit
當?shù)趇個bit潮罪，出現(xiàn)第三次，將ones和twos的第i個bit都清為0领斥，ones的最終值就是answer嫉到。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ones, twos, threes = 0, 0, 0
for num in nums:
twos |= ones & num
ones ^= num
threes = ones & twos
ones &= ~threes
twos &= ~threes
return ones
