Single Number III


  • 3
    N

    Given an array of integers, every element appears twice except for two. Find that single two.

    Note:
    Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

    //spoiler
    If you know the xor method of the "Single Number I", please think about the properties of xor of the two numbers.

    //Best solution:

    1. x = xor of each element in the list ==> x = a xor b
    2. a != b => there are at least one 1-bit in x
    3. take an arbitrary 1-bit (which means a and b is different on this bit), the elements in the array can be classified into two groups: one of them contains a, the other contains b.
    4. a = xor of each element in the list which the corresponding bit = 0
    5. b = a xor x

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.