Single Number III

题目描述

Given 2*n + 2 numbers, every numbers occurs twice except two, find them.

Example Given [1,2,2,3,4,4,5,3] return 1 and 5

Challenge O(n) time, O(1) extra space.

解题方法

  • 全部异或，然后对结果找到第一个为1的bit, 这个bit必然是两个single number不一样的Bit
  • 对于这个bit,将原来的数组分为两组
  • 然后再按照single number的方法分别找到两个数

不用extra space的做法

我们已经知道消去从右到左第一个1 bit的方法是x & (x-1), 那么我们将x-1 的bit flip一下变为~(x-1), 再x & (~(x-1)),就可以 得到一个只有这一个bit位1的mask, 然后通过这个mask来直接在loop中分组做xor, 就像single number i一样可以找到两个single number

Solution

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []

        xor = 0
        for num in nums:
            xor ^= num

        a = 0
        b = 0
        bitMask = xor & (~(xor-1))
        for num in nums:
            if num & bitMask:
                a ^= num
            else:
                b ^= num

        return [a, b]

Reference