剑指offer（Java实现）56 - 数组中只出现一次的两个数字

数组中只出现一次的两个数字-56-1

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

样例

输入：[1,2,3,3,4,4]
输出：[1,2]

思路：

先依次异或，出现两次的数字都会变成0，两个只出现一次的数字肯定至少有一位是不同的，找到这一位，用来把数组分成两部分，然后分别异或，即可得到结果。

class Solution {
    public int[] singleNumber(int[] nums) {
        int res = 0;
        for(int num : nums) res ^= num;
        int index = 1;
        while((res & index) == 0) index <<= 1;
        int[] ans = new int[2];
        for(int num : nums){
            if((num & index) != 0)
                ans[0] ^= num;
            else ans[1] ^= num;
        }
        return ans;
    }
}