Single Number II

Question

• leetcode: Single Number II | LeetCode OJ
• lintcode: (83) Single Number II

Problem Statement

Given 3*n + 1 numbers, every numbers occurs triple times except one, find it.

Example

Given [1,1,2,3,3,3,2,2,4,1] return 4

Challenge

One-pass, constant extra space.

题解1 - 逐位处理

上题 Single Number 用到了二进制中异或的运算特性，这题给出的元素数目为3*n + 1，因此我们很自然地想到如果有种运算能满足「三三运算」为0该有多好！对于三个相同的数来说，其相加的和必然是3的倍数，仅仅使用这一个特性还不足以将单数找出来，我们再来挖掘隐含的信息。以3为例，若使用不进位加法，三个3相加的结果为：

0011
0011
0011
----
0033

注意到其中的奥义了么？三个相同的数相加，不仅其和能被3整除，其二进制位上的每一位也能被3整除！因此我们只需要一个和int类型相同大小的数组记录每一位累加的结果即可。时间复杂度约为 $$O((3n+1)\cdot sizeof(int) \cdot 8)$$

Python

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

        result = 0
        for i in xrange(32):
            bit_i_sum = 0
            for num in nums:
                bit_i_sum += ((num >> i) & 1)
            result |= ((bit_i_sum % 3) << i)
        return self.twos_comp(result, 32)

    def twos_comp(self, val, bits):
        """
        compute the 2's compliment of int value val
        e.g. -4 ==> 11100 == -(10000) + 01100
        """
        return -(val & (1 << (bits - 1))) | (val & ((1 << (bits - 1)) - 1))

*