645 错误的集合（奇淫技巧）-蒲公英云

645 错误的集合（奇淫技巧）

1. 问题描述：

集合 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.com/problems/set-mismatch

2. 思路分析：

最简单的方法是使用哈希表来统计各个数字出现的次数，找出出现次数为0与出现次数为2的数字即可。其实这里我们可以不使用哈希表来记录各个数字出现的次数，我们可以将数字出现的次数存储在原数组中，这样可以节省一定的空间，怎么样才能够在不丢失原来数组信息的前提下来判断数字出现的次数呢？这里对数组元素取反即可实现，我们在遍历的时候可以对当前的nums[i]对应的位置的数字取反，这样当我们发现当前遍历的元素为负数的时候说明之前已经出现过一次的，也即当前遍历的数字就是次数为2的数字，当遍历完整个数组之后那么出现次数为0和次数为2的位置都为正数，我们再遍历一遍数组，找出另外一个数字即可，我们在找的时候先找出为正数的元素，判断当前的位置是否是出现次数为2的元素，如果不是那么肯定是出现次数为0的元素，扫描两遍即可知道答案。

3. 代码如下：

from typing import List
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        res = [0, 0]
        for x in nums:
            # 因为某个可能当前的数字之前已经取反了所以需要取它的绝对值
            x = abs(x)
            # 当数组元素小于0之后说明之前已经出现过一次
            if nums[x - 1] < 0:
                res[0] = x
            nums[x - 1] *= -1
        # 最终出现0次与出现2次的位置都为正数, 我们需要找出另外一个不是出现次数为2的位置即可
        for i in range(len(nums)):
            if nums[i] > 0 and i + 1 != res[0]:
                res[1] = i + 1
                return res