一堆数字, 有一个数字只出现一次, 其他数字都出现3次, 找到这个数字, 要求在线性时间和常数空间复杂度解决这个问题.
前置问题是136, 这道题我的想法是,
首先还是要通过位运算来解决这个问题, 我要构建一个计数器一样的东西.当这个位上的数字出现一次, 以三为模来进行计算. 这样就可以解决. 为此我用了三个计数器, a,b,c.
初始值 a=0, b=0, c=~0, 不断累计. 对于某一位而言, 1在a, b, c 上只出现一次, 出现在a上说明出现3n +1次, 出现在b上说明3n +2 次, c上说明出现3n 次.
`class Solution:
def singleNumber(self, nums: List[int]) -> int:
a, b = 0, 0
c = ~0
for i in nums:
tmp = ~i
a, b, c = (c & i) | (a & tmp) , a & i | (b & tmp), b & i | (c & tmp)
return a | b`