题目

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1：

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

示例 2：

输入：nums = [1,1]
输出：[1,2]

位运算

位运算的特点：

• 满足交换律和结合律
• 相同为0，相异为1
• $a \oplus a = 0$
• $a \oplus 0 = a$

使用位运算，可以达到 $O(n)$ 的时间复杂度和 $O(1)$ 的空间复杂度。

突破口
假设 x 为重复元素，y 缺失元素

数组中所有元素 + 从 1 到 n 所有元素

以上所有元素中，x 出现 3 次，y 出现 1 次，其余均出现 2 次

以上所有元素进行异或运算，等价于$x \oplus y$

思路
第一步，计算$x \oplus y$，记为 xor
第二步，计算 x 和 y 的二进制表示中的最低不同位，记为 lowbit
第三步，把所有元素按照与 lowbit进行与运算结果是否为 0 分成两组
第四步，每一组的元素都进行异或运算，最后得到两个数，num1 和 num2，一个重复，一个缺失
第五步，能在原数组中找到的数为重复，另一个是缺失的数

public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int xor = 0;
        // 数组中所有元素 进行异或 （一个缺失，一个重复）
        for (int num : nums) {
            xor ^= num;
        }
        // 1-n 进行异或 （缺失1次，重复3次，其余均为2次）
        for (int i = 1; i <= n; i++) {
            xor ^= i;
        }
        // lowbit 为 x 和 y 的二进制表示中的最低不同位
        int lowbit = xor & (-xor);
        int num1 = 0, num2 = 0;
        for (int num : nums) {
            if ((num & lowbit) == 0) {
                num1 ^= num;
            } else {
                num2 ^= num;
            }
        }
        for (int i = 1; i <= n; i++) {
            if ((i & lowbit) == 0) {
                num1 ^= i;
            } else {
                num2 ^= i;
            }
        }
        //此时 num1和num2 一个是x，一个是y
        //遍历数组，如果能找到num1 则num1为重复的数字，否则num2为重复的数字
        for (int num : nums) {
            if (num == num1) {
                return new int[]{num1, num2};
            }
        }
        return new int[]{num2, num1};
    }