错误的集合

645. 错误的集合

难度：简单

集合 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

原地哈希表

class Solution {
    public int[] findErrorNums(int[] nums) {

        int n = nums.length;
        int res [] = new int[2];
        for(int i=0;i<n;i++){
            int index = Math.abs(nums[i]) - 1;
            if(nums[index]>0){
                nums[index] = -nums[index];
            }else{
                res[0] = Math.abs(nums[i]);
            }
        }

        for(int i=0;i<n;i++){
            if(nums[i]>0){
                int num = i+1;
                res[1] = num;  
            }
        }
        return res;
    }
}

查找重复元素

遍历数组的每个元素，将当前遍历的元素 $c$ 作为 $index$ ，使 $nums[index]*=-1$,遍历下一个元素时，判断下一个元素 $c$ 作为 $index$ 时, $nums[index]$ 是否小于 $0$ ,如果小于 $0$说明元素c已经被遍历过了，是重复元素

查找丢失元素

再次遍历修改后的数组，如果修改后的数组中某个值不小于0，说明这个index没有被遍历到，也就是原数组中没有这个值（因为index就是遍历的值）

class Solution {
    public int[] findErrorNums(int[] nums) {
        int dup = 0;
        for (int val : nums) {
            if (nums[Math.abs(val) - 1] < 0) {
                dup = Math.abs(Math.abs(val));
            } else {
                nums[Math.abs(val) - 1] *= -1;
            }
        }

        int missing = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                missing = i + 1;
            }
        }

        return new int[]{dup, missing};
    }
}

异或运算

通过异或运算对数字分组，类似于前面做的剑指 Offer 56 - I. 数组中数字出现的次数

public class Solution {
    public int[] findErrorNums(int[] nums) {
        int xor = 0, xor0 = 0, xor1 = 0;
        for (int n: nums)
            xor ^= n;
        for (int i = 1; i <= nums.length; i++)
            xor ^= i;
        int rightmostbit = xor & ~(xor - 1);
        for (int n: nums) {
            if ((n & rightmostbit) != 0)
                xor1 ^= n;
            else
                xor0 ^= n;
        }
        for (int i = 1; i <= nums.length; i++) {
            if ((i & rightmostbit) != 0)
                xor1 ^= i;
            else
                xor0 ^= i;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == xor0)
                return new int[]{xor0, xor1};
        }
        return new int[]{xor1, xor0};
    }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/set-mismatch/solution/cuo-wu-de-ji-he-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信