1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

https://leetcode.cn/problems/set-mismatch/description/

2.解题方法

2.1.解题思路

位运算

2.2.解题步骤

第一步，记a,b分别为重复出现的整数和缺失的整数，记nums_=nums+[1,2,...,n]，则将nums_中所有数做异或运算，最终得到的值即为a^b

第二步，使用a^b的最低位将nums_分为两组，两组数分别做异或运算，最终的值是a,b或b,a

第三步，遍历一遍nums，确定a,b中缺失和重复的数

3.解题代码

python代码

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        # 思路：位运算
        # 第一步，记a,b分别为重复出现的整数和缺失的整数，记nums_=nums+[1,2,...,n]，则将nums_中所有数做异或运算，最终得到的值即为a^b
        n = len(nums)
        nums_ = nums + list(range(1, n + 1))
        ans = 0
        for num in nums_:
            ans ^= num
        # 第二步，使用a^b的最低位将nums_分为两组，两组数分别做异或运算，最终的值是a,b或b,a
        lowbit = ans & (-ans)
        a, b = 0, 0
        for num in nums_:
            if num & lowbit:
                a ^= num
            else:
                b ^= num
        # 第三步，遍历一遍nums，找到a,b中缺失和重复的数
        if a in nums:
            return [a, b]
        else:
            return [b, a]

4.执行结果