[LeetCode#260]Single Number III

Problem:

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Analysis:

Sort a array is always a good beginning to find duplciates in a array.
But it would at least take O(nlogn) time in sorting the array. 

Solution 1:
Basic idea:
step 1: sort the entire array.
step 2: in the sorted form, if a element does not have neighors share the same value wit it. It must be the single element we want to find. 
Note: take care the first and last element, it may incure out of bound exception. 

public int[] singleNumber(int[] nums) {
        if (nums == null || nums.length <= 1)
            return new int[0];
        Arrays.sort(nums);
        int[] ret = new int[2];
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            boolean is_single = true;
            if (i != 0) 
                is_single = is_single && (nums[i] != nums[i-1]);
            if (i != nums.length - 1)
                is_single = is_single && (nums[i] != nums[i+1]);
            if (is_single)
                ret[count++] = nums[i];
        }
        return ret;
}
 
Wrong logic:
If you use the default value of flag as "true", you must take care the logic you are going to implment. (|| or &&)
Initially, I have implemented following problemetic logic
-------------------------------------------------------------------
        for (int i = 0; i < nums.length; i++) {
            boolean is_single = true;
            if (i != 0) 
                is_single = is_single || (nums[i] != nums[i-1]);
            if (i != nums.length - 1)
                is_single = is_single || (nums[i] != nums[i+1]);
            if (is_single) {
                ret[count] = nums[i];
                count++;
            }
        }
-------------------------------------------------------------------

In the above code, the is_single would alway be true, since the intial default is true and I use "||" to pass around logic. 
What I meant to do is "once it has a neighor, it should return false, and pass to the value".
The change is easy:
is_single = is_single && (nums[i] != nums[i-1]);


Even though the above solution is clear, there could a very elegant and genius solution for this problem. 
But it requires strong understand of bit operation. 
Key: 
The magic rule of XOR. 
a ^ a = 0; 
a ^ b ^ a = 0;
a ^ b ^ c ^ a = b ^ c; 
After the XOR operation, all numbers appear even times, would be removed from the final XOR value.
What's more, after "a ^ b ^ c ^ a = b ^ c", the set bits of "b ^ c" would only contain the digits that b are different from c. 

Solving step:
step 1: XOR all elements in the array.

int xor = 0; 
for (int i = 0; i < nums.length; i++) {
    xor ^= nums[i];
}

step 2: get the rightmost bit of the set bit.
right_most_bit = xor & (~(xor-1));

step 3: divide the nums array into two set based on the set bit. (thus the single numbers: b, c would be placed into two different set). Then XOR at each set and get those two numbers.
for (int i = 0; i < nums.length; i++) {
    if ((nums[i] & right_most_bit) == 0) {
        ret[0] ^= nums[i];
    } else{
        ret[1] ^= nums[i];
    }
}


Skills:
1. how to get the rightmost set bit?
right_most_bit = xor & (~(xor-1));
Reason:
The xor-1 would turn the rightmost set bit into 0, and bits after it becomes 1.
'1000001000' => '1000000111'
The not "~" operation would turn all bits into opposite bit (note the rightmost bitset has already been setted into 0)
'1000000111' => '0111111000'
The '&' operation would filter the setbit out. 
'0111111000'
'1000001000'
'0000001000'

2. The set bit could be used a proper indicator to divide the original array into two sets.
if ((nums[i] & right_most_bit) == 0) {
    ret[0] ^= nums[i];
} else{
    ret[1] ^= nums[i];
}
Note the form of set bit: '0000001000', only the number share the same bit would not equal to "000000000...(integer: 0)"

Solution:

public class Solution {
    public int[] singleNumber(int[] nums) {
        if (nums == null || nums.length == 0)
            return new int[0];
        int[] ret = new int[2];
        int xor = 0, right_most_bit = 0; 
        for (int i = 0; i < nums.length; i++) {
            xor ^= nums[i];
        }
        right_most_bit = xor & (~(xor-1));
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & right_most_bit) == 0) {
                ret[0] ^= nums[i];
            } else{
                ret[1] ^= nums[i];
            }
        }
        return ret;
    }
}

[LeetCode#260]Single Number III

相关推荐