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)"

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;

    }

}