题目

一个整型数组 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]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof

异或运算：相同位为0，不同位为1

思路：所有数字异或 = 不同的那两个数字异或
我们先得到所有数字异或的结果，假如为100110，
从右往左取第三位数字，按照这个将一组数据分为两组
那么每组中都必定有一个不同的数字

代码

        public int[] singleNumbers(int[] nums) {
            int mid = 0;
            //1.找到两个不同的数字异或的结果
            for (int i = 0; i < nums.length; i++) {
                mid = mid^nums[i];
            }
            //2.得到mid变为二进制从右往左的第一个不同
            int j = 0;
            for (int i = 0; i < 32; i++) {
                if ((mid>>i & 0x01) == 1){
                    j = i;
                    break;
                }
            }
            //3.遍历将原数组分为两部分
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                if ((nums[i] >> j & 0x01) == 1){
                    list1.add(nums[i] );
                }else {
                    list2.add(nums[i]);
                }
            }
            //4.在两个分开的数组中找到不同的数字
            int[] ans = new int[2];
            for (int i = 0; i < list1.size(); i++) {
                ans[0] = ans[0] ^ list1.get(i);
            }
            for (int i = 0; i < list2.size(); i++) {
                ans[1] = ans[1] ^ list2.get(i);
            }
            return ans;
        }