[数据结构与算法]《leetcode》645. 错误的集合《位操作》

645. 错误的集合

难度简单213

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

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

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

示例 1：

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

示例 2：

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

提示：

• 2 <= nums.length <= 104
• 1 <= nums[i] <= 104

解析：

? 位操作，首先把1到n和数组元素全异或可以得到xor=x^ x ^ x ^y= x^y, 然后通过tmp=xor & (-xor), 可以得到x和y不同的位数的最低位，可以通过与tmp进行与操作，把x和y分开；最后通过比较数组元素确定那个是多的，那个是没有的。

代码：

class Solution {
   public int[] findErrorNums(int[] nums) {
       int n=nums.length;
       if(n<=1)
           return new int[2];
       //O(n) O(1)
       int xor=0;
       for(int i=0;i<n;i++)
       {
           xor^=(i+1);
           xor^=nums[i];
       }
       xor&=(-xor);//xor=x^y, tmp=xor&(-xor) tmp:x和y的二进制表示中的最低不同位,可以用来区分num1和num2
       int num1=0,num2=0;
       for(int i=0;i<n;i++)
       {
           if(((i+1)&xor)==0)
               num1^=(i+1);
           else
               num2^=(i+1);
           if(((nums[i])&xor)==0)
               num1^=nums[i];
           else
               num2^=nums[i];
       }
       for(int num:nums)
       {
           if(num==num1)
               return new int[] {num1,num2};
       }
       return new int []{num2,num1};

   }
}