260. 只出现一次的数字 III

exiaohu 于 2021-10-30 发布

题目链接:260. 只出现一次的数字 III

按照异或的性质,x^x=0, x^0=x,其中 x 为任意数字。异或具有交换律、结合律。

class Solution:
   def singleNumber(self, nums: List[int]) -> List[int]:
       xorVal = 0
       for num in nums:
           xorVal ^= num

       # x ^ y == xorVal
       target = 0
       for i in range(32):
           if (1 << i) & (xorVal) != 0:
               target = 1 << i
               break

       x, y = 0, 0
       for num in nums:
           if num & target == 0:
               x = x ^ num
           else:
               y = y ^ num
       return [x, y]