260. Single Number III - jiejackyzhang/leetcode-note GitHub Wiki

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:

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

Array类题目。

我们知道如果只有一个single number，则将数组中所有元素做异或操作即可得到。 因此这里的关键是如何转换为上述问题。

这里将数组中所有元素做异或操作，得到两个single number的异或。 我们知道这两个数不同，则它们的异或必然有一位为1。 我们可以通过twoXOR & -twoXOR的操作得到最右边的1。 这样，就可以把数组中的元素分为两大类，一类为这一位为1，另一类为这一位为0。 而两个single number则分别在这两大类中。 这样，问题就转化为在一个数组中找唯一一个single number的问题了。

public class Solution {
    public int[] singleNumber(int[] nums) {
        // get XOR of two single numbers
        int twoXOR = 0;
        for(int num : nums) {
            twoXOR ^= num;
        }
        // get its last set bit
        int setBit = twoXOR & -twoXOR;
        int[] res = new int[2];
        for(int num : nums) {
            if((num & setBit) == 0) {
                res[0] ^= num;
            } 
        }
        res[1] = twoXOR ^ res[0];
        return res;
    }
}