Leetcode: Single Number III

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?

如果对所有元素进行异或操作，最后剩余的结果是出现次数为1次的两个数的异或结果，此时无法直接得到这两个数具体的值。但是，因为这两个数一定是不同的，所以最终异或的值至少有一个位为1。我们可以找出异或结果中第一个值为1的位，然后根据该位的值是否为1，将数组中的每一个数，分成两个部分。这样每个部分，就可以采用Sing number I中的方法得到只出现一次的数。

Code (Java):

public class Solution {
    public int[] singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        
        int xor = 0;
        
        // Step 1: calculate the xor for all numbers
        // So the result is the xor of the two single numbers
        for (int num : nums) {
            xor ^= num;
        }
        
        // Step 2: find the first bit 1 from right
        int mask = 1;
        while ((mask & xor) == 0) {
            mask = mask << 1;
        }
        
        int xor1 = 0;
        int xor2 = 0;
        
        for (int num : nums) {
            if ((num & mask) == 0) {
                xor1 ^= num;
            } else {
                xor2 ^= num;
            }
        }
        
        int[] result = new int[]{xor1, xor2};
        
        return result;
    }
}