难度: Easy
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1：
输入：nums = [1,2,2,4] 输出：[2,3]
示例 2：
输入：nums = [1,1] 输出：[1,2]
提示：
2 <= nums.length <= 1041 <= nums[i] <= 104运行时间: 59 ms
内存: 17.0 MB
class Solution:
def findErrorNums(self, nums: List[int]) -> List[int]:
dup = 0
miss = 0
n = len(nums)
# 确定重复元素
# 注意索引偏移
for i in range(n):
j = abs(nums[i])
if nums[j-1] < 0:
dup = j
else:
nums[j-1] *= -1
# 确定缺失元素
for i in range(n):
if nums[i] > 0:
miss = i+1
break
return [dup, miss] if dup and miss else []
本题解使用了两次遍历。第一次遍历数组，利用负号标记法找出重复的元素。具体做法是，遍历到某个元素 nums[i] 时，将 nums[abs(nums[i])-1] 取反。如果发现取反后的值为负数，说明之前已经遍历过该位置，即 abs(nums[i]) 就是重复的元素。第二次遍历数组，找出仍为正数的位置 i，说明 i+1 就是缺失的数字。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findErrorNums(self, nums: List[int]) -> List[int]:
dup = 0
miss = 0
n = len(nums)
# 确定重复元素
# 注意索引偏移
for i in range(n):
j = abs(nums[i])
# 如果 nums[j-1] 已经是负数，说明之前遍历过，j 就是重复元素
if nums[j-1] < 0:
dup = j
# 否则将 nums[j-1] 取反，标记该位置已遍历过
else:
nums[j-1] *= -1
# 确定缺失元素
for i in range(n):
# 如果 nums[i] 仍为正数，说明 i+1 是缺失的数字
if nums[i] > 0:
miss = i+1
break
return [dup, miss] if dup and miss else []
在第一次遍历中，通过将数组中某个索引位置的值变为其相反数（即负数），来标记该位置对应的数字已经被访问过。具体来说，当遍历到数字 nums[i] 时，将索引 abs(nums[i])-1 的位置的值取反。如果在取反之前，这个位置的值已经是负数，这表明之前已经访问过该位置，因此 abs(nums[i]) 就是重复访问的数字。这种方法通过在原数组上直接修改，避免了额外的空间使用，非常高效。
在第二次遍历中，检查哪些索引位置的值仍然是正数。由于之前的遍历中我们将访问过的数字对应的索引位置的值标记为负数，如果某个索引位置 i 的值仍然是正数，这意味着数字 i+1 没有在第一次遍历中被访问过，因此 i+1 就是缺失的数字。这种方法可以确保找到所有类型的缺失数字，只要数组的长度是正确的，即1到n。
如果输入数组中的数字超出了1到n的范围，本题解可能不再有效。这是因为算法假设所有数字都在1到n之间，并且使用数字值作为数组索引（通过减1来调整）。超出范围的数字可能导致数组索引越界，或者无法正确标记数字。因此，对于包含超出范围数字的数组，需要先验证所有数字是否在1到n之间，或者使用其他方法来处理这种情况。
使用负号标记法确实会修改原数组的值，但这种修改是算法设计的一部分，并不会影响到找出重复或缺失数字的准确性。第一次遍历用于标记访问过的数字，而第二次遍历检查哪些位置未被标记（即值仍为正）。只要所有操作都按照设计执行，修改原数组值不会对结果产生不利影响。不过，这种方法的一个缺点是它改变了原数组，这在某些情况下可能是不可接受的。