剑指Offer--Java--数组中只出现一次的两个数字

题目描述

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

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

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

样例描述

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

输出：[1,2]

思路

1. 假如只有一个数出现一次，其他数都出现两次，直接异或就行
2. 将所有数异或一遍，假设只有x，y只出现一次，最后结果得到x^y
   这个结果肯定不为0(否则x==y)，则二进制表示中至少有一位是1，则该位在x和y的二进制中一定是不同的，找到这么一个第k位
3. 利用2中的某位，将所有数划分为两个集合（该位是1的集合，该位是0的集合），则x和y一定不在同一个集合，且所有相同的数一定属于同一个集合。 此时本题就简化成了1中的情况，将第一个集合中所有数异或得到x，第二个集合中所有数异或得到y
4. 主要用到异或的性质：相同数位异或为0，不同数位异或为1，0和任何数异或都是任何数，异或运算具有交换律和结合律

代码

class Solution {
    public int[] findNumsAppearOnce(int[] nums) {
        int sum = 0; //x ^ y
        for (int x: nums) sum ^= x; //0异或任何数得任何数
        int k = 0;
        //sum右移k位相当于把第k位右移到个位，然后和1异或判断该位是0还是1
          //寻找一个为1的位，存在k
        while((sum >> k & 1) == 0) k++;
        int first = 0;
        for (int  x: nums){
            //表示找到所有第k位是1的数的集合
            if ((x >> k & 1) == 1)
            first ^= x;    //第一个数就是first，第二个数不用再次计算，直接sum ^ first 因为sum = first ^second
            //相当于把first消除掉剩下second
        }
    return new int[]{first, sum ^ first};
    }
}