java数据结构与算法刷题-----LeetCode645. 错误的集合

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846

法一：桶排序思想

解题思路

1. 题目说，每个集合的值都是1 ~ n，一般我们会想到将数组中元素，挨个作为key放入map中，然后遍历1~n从map中获取value，看看谁是0，谁是2.
2. 但是我们可以直接再创建一个数组，长度为n+1，用下标来代表数字，将1~n的个数，放入桶中。比如遍历nums数组是，当前元素是1，就放入下标为1的桶中，此时这个桶有1个元素，当我们有遍历到1时，再次放入下标为1的桶，此时这个桶有2个元素。
   

代码:时间复杂度O(n) 空间复杂度O(n)

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] ans = new int[2];//答案要求返回形式
        int[] bucket = new int[nums.length + 1];//桶排序的思想，因为nums中的值固定为1~n
        for (int num : nums) bucket[num]++;//将数组中的值，放入对应的桶
        for (int i = 1; i <= nums.length; i++) {//依次遍历1~n
            if (bucket[i] == 0) ans[1] = i;//如果当前桶中元素个数为0，说明集合缺少这个元素
            else if (bucket[i] == 2) ans[0] = i;//如果当前桶有2个元素，说明集合中这个值有重复
            if (ans[0] != 0 && ans[1] != 0) break;//如果已经找到答案，就无需继续遍历了
        }
        return ans;//返回答案
    }
}

法二：位运算

代码:时间复杂度O(n) 空间复杂度O(1)

class Solution {
    public int[] findErrorNums(int[] nums) {
        //异或 两个数相同异或为0，两个数不同异或为1
        //任何数a异或0，都等于a本身。0 ⊕ a = a 
        //两个相同的数异或必然为0。a ⊕ a = 0;
        //最关键的是，异或具有结合律。0⊕1⊕2⊕2 = (0⊕1)⊕(2⊕2) = 1 ⊕ 0 = 1; 
        int n = nums.length;
        int xor = 0;
        //保存去掉重复（偶数个）元素后，剩余元素的异或结果。
        for(int num:nums) xor ^= num;
        //xor整体异或1~n，这样剩下的就是重复的元素，和不存在的元素的异或结果
        for(int i = 1;i<=n;i++) xor^=i;
        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;
        }
        for(int num:nums){
            if(num==num1) return new int[]{num1,num2};
        }
        return new int[]{num2,num1};
    }
}