260. Single Number III

解題說明

C++ 解法

複雜度分析

虛擬碼

Function singleNumber(nums):
    // Step 1: XOR all elements to get a XOR b
    diff = 0
    For each x in nums:
        diff = diff XOR x

    // Step 2: Isolate the lowest set bit of diff
    //         This bit differs between a and b
    mask = diff AND (-diff)

    // Step 3: Split into two groups by mask, XOR each group
    a = 0, b = 0
    For each x in nums:
        If x AND mask is non-zero:
            a = a XOR x
        Else:
            b = b XOR x

    Return [a, b]

其他解法

延伸思考