Single Number II

medium, bit manipulation

Question

有一个整数序列，其中的每个整数除了一个都出现了3次，找到那个落单的数。

Notes

Time complexity要求O(n)且不能分配新memory

Solution

使用bit操作来解答. 将所有数的第i个bit相加，再模3的结果必然是0或者1，因为数字要么出现3次要么出现1次。然后使用或运算来找到单数。

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表示出现一次的第i个bit
twos -- bitmask表示出现两次的第i个bit
threes -- bitmask表示出现三次的第i个bit
当第i个bit，出现第三次，将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