#左耳听风 ARST 打卡活动重启#
目录
一、问题
二、解题方法一
三、解题方法二
四、区别
关于 ARTS 的释义 —— 每周完成一个 ARTS：
● Algorithm: 每周至少做一个 LeetCode 的算法题
● Review: 阅读并点评至少一篇英文技术文章
● Tips: 学习至少一个技术技巧
● Share: 分享一篇有观点和思考的技术文章
希望通过此次活动能聚集一波热爱技术的人，延续好奇、探索、实践、分享的精神。
一、问题
集合 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
二、解题方法一
def findErrorNums(nums):
n = len(nums)
error_nums = [0] * n
repeat_num = -1
for i in range(n):
if nums[abs(nums[i]) - 1] > 0:
error_nums[abs(nums[i]) - 1] = abs(nums[i])
else:
repeat_num = abs(nums[i])
return [x for x in range(1, n + 1) if x not in error_nums] + [repeat_num]
这段代码实现了一个函数 `findErrorNums`,用于找出给定数组 `nums` 中重复出现的整数和丢失的整数，并将它们以数组的形式返回。
具体实现过程如下：
1. 首先定义一个长度为 `n` 的列表 `error_nums`,其中 `error_nums[i]` 表示在 `nums` 中第 `i` 个元素对应的错误数字。初始时，所有元素都设为 0。
2. 然后遍历整个数组 `nums`,依次判断每个元素是否出现了错误。如果某个元素的绝对值在 `nums` 中出现过，说明它出现了错误，将该元素的绝对值赋值给 `error_nums` 中对应位置的元素；否则，说明该元素是重复出现的数字，将其赋值给变量 `repeat_num`。
3. 最后，遍历从 1 到 `n` 的所有整数，如果某个整数不在 `error_nums` 中，说明它是正确的数字，将其加入结果数组中；否则，说明它是丢失的数字，将其加入结果数组中。
4. 返回结果数组即可。
总的来说，这段代码的时间复杂度为 O(n),空间复杂度为 O(n)。
三、解题方法二
另一种解题方法是使用哈希表来记录每个数字出现的次数，然后遍历整个数组，找出重复出现的数字和丢失的数字。
具体实现过程如下：
1. 首先定义一个长度为 `n` 的列表 `nums`,其中 `nums[i]` 表示集合 S 中第 `i` 个元素。
2. 创建一个空的哈希表 `count`,用于记录每个数字出现的次数。
3. 遍历整个数组 `nums`,依次将每个数字加入哈希表中，并更新该数字的出现次数。如果某个数字已经在哈希表中出现过，说明它出现了两次，需要将其从哈希表中删除。
4. 遍历哈希表，找出出现次数为奇数的数字，即为重复出现的数字；遍历数组 `nums`,找出第一个不在哈希表中的数字，即为丢失的数字。
5. 将重复出现的数字和丢失的数字以数组的形式返回即可。
总的来说，这种方法的时间复杂度为 O(n),空间复杂度为 O(n)。
def findErrorNums(nums):
count = {}
for num in nums:
if num in count:
count[num] += 1
else:
count[num] = 1
res = []
repeat_num = None
for num, occ in count.items():
if occ % 2 == 1:
if repeat_num is not None:
return [repeat_num, num]
repeat_num = num
elif occ == 1:
res.append(num)
return [res[0], res[1]] if len(res) == 2 else []
四、区别
哈希表和双指针的区别在于，哈希表是一种数据结构，它提供了快速的插入操作和查找操作，无论哈希表中有多少条数据，插入和查找的时间复杂度都是为O(1)。而双指针则是一种算法思想，它通过两个指针来遍历数组或链表，从而找到符合条件的元素。 文章来源：https://www.toymoban.com/news/detail-620749.html
文章来源地址https://www.toymoban.com/news/detail-620749.html
到了这里，关于打卡力扣题目十一的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
