645.错误的集合

错误的集合

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

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

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

示例 1：

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

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

提示：

\(2 <= nums.length <= 10^4\)
\(1 <= nums[i] <= 10^4\)

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/set-mismatch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路1：哈希表

这个没啥好说的。

code

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();

        vector<int> cnt(n + 1,0);

        for(auto item : nums) cnt[item] ++;

        vector<int> ans(2,0);

        for(int i = 1;i <= n;i ++)
        {
            if(cnt[i] == 0) ans[1] = i;
            if(cnt[i] == 2) ans[0] = i;

        }

        return ans;
    }
};

位运算

为了在常数空间内实现，需要使用位运算，实际上像是这种出现偶数次的通常可以考虑使用异或消除，但是本文中出现偶数次的是重复的数字，也是最后的结果，我们并不希望消除掉，怎么办呢？

1. 在数组中添加1-n,这样重复的数字和缺失的数字都是奇数次，其余数字都是偶数次
2. 全部异或就可以将其余数字全部去除
3. 记x为重复的数字，y为缺失的数字，最后的结果为x ^ y
4. 如何在2n个数字中找到x和y呢
5. lowbit(x ^ y)为x和y的最低不同位，根据最低不同位区分x和y，将2n个数字都分到两个不同的组别中，同时每个组中可以通过异或消除重复的数字，找到x和y
6. 最后判别x和y哪个是重复的哪个是缺失的

code

class Solution {
public:

    int lowbit(int x)
    {
        return x & (-x);
    }

    vector<int> findErrorNums(vector<int>& nums) {

        int n = nums.size();

        int xy = 0;

        for(auto item : nums) xy = xy ^ item;

        for(int i = 1;i <= n;i ++) xy = xy ^ i;

        int diff = lowbit(xy);

        int nums1 = 0,nums2 = 0;

        for(auto item : nums)
        {
            if((item & diff) == 0) nums1 ^= item;
            else nums2 ^= item;
        }

        for(int i = 1;i <= n;i ++)
        {
            if((i & diff) == 0) nums1 ^= i;
            else nums2 ^= i;
        }

        for(auto item : nums)
        {
            if(item == nums1) return {nums1,nums2};
        }

        return {nums2,nums1};


    }
};