C O(n)-time O(1)-space 7-line Solution with Detail Explanation


  • 23
    N
    int* singleNumber(int* nums, int numsSize, int* returnSize) {
        int i, *ret = calloc(*returnSize = 2, sizeof(int));
        for(i = 0; i < numsSize; ret[0] ^= nums[i++]);
        for(i = 0; i < numsSize; i++)
            if(nums[i] & ret[0] & -ret[0])
                ret[1] ^= nums[i];
        ret[0] ^= ret[1];
        return ret;
    }
    

    However I posted this question some days ago at https://leetcode.com/discuss/48119/single-number-iii .

    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 according to this bit: 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

  • 0
    O

    damn cleverrrrr 3Q for sharing


Log in to reply
 

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