剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：

2 <= nums.length <= 10000

class Solution {
    public int[] singleNumbers(int[] nums) {

        //只出现一次的数据 使用异或运算
        //异或运算满足 a^a = 0 ;a^b = b^a 
        //所以有 a^a^b^b^.....x^z^z = 0^0^x^0 = x;
        


        int x = 0, y = 0, n = 0, m = 1;
        for(int num : nums)               // 1. 遍历异或得到n = x^y
            n ^= num;


            //根据异或运算定律，n为1的位 即为 x与y不同的位
        while((n & m) == 0)               // 2. 循环左移，计算 m
            m <<= 1;    //这里的m 00000010000，这里的1即为x与y第一个不同的位
                        //例如 x = 0010 y = 0001 则 m = 0010 因为他们的低2位不一样



        //使用m就可以将数组分为2组，相同的数字一定会在同一组中，xy一定不会在同一组中
        //以上面的m为例，一组为低2位为0的组，一组为低2位为1的组，x与y一定均匀分布在这两组中，不会在同一组出现
        for(int num: nums) {              // 3. 遍历 nums 分组
            if((num & m) != 0) x ^= num;  // 4. 当 num & m != 0 
            else y ^= num;                // 4. 当 num & m == 0
        }

        return new int[] {x, y};          // 5. 返回出现一次的数字
    }
}