英文原文
You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.
You are given an integer array nums representing the data status of this set after the error.
Find the number that occurs twice and the number that is missing and return them in the form of an array.
Example 1:
Input: nums = [1,2,2,4] Output: [2,3]
Example 2:
Input: nums = [1,1] Output: [1,2]
Constraints:
2 <= nums.length <= 1041 <= nums[i] <= 104
中文题目
集合 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
通过代码
高赞题解
计数
一个朴素的做法是，使用「哈希表」统计每个元素出现次数，然后在 $[1, n]$ 查询每个元素的出现次数。
在「哈希表」中出现 $2$ 次的为重复元素，未在「哈希表」中出现的元素为缺失元素。
由于这里数的范围确定为 $[1, n]$，我们可以使用数组来充当「哈希表」，以减少「哈希表」的哈希函数执行和冲突扩容的时间开销。
代码：
[]class Solution { public int[] findErrorNums(int[] nums) { int n = nums.length; int[] cnts = new int[n + 1]; for (int x : nums) cnts[x]++; int[] ans = new int[2]; for (int i = 1; i <= n; i++) { if (cnts[i] == 0) ans[1] = i; if (cnts[i] == 2) ans[0] = i; } return ans; } }
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
数学
我们还可以利用数值范围为 $[1, n]$，只有一个数重复和只有一个缺失的特性，进行「作差」求解。
- 令 $[1, n]$ 的求和为 $tot$，这部分可以使用「等差数列求和公式」直接得出：$tot = \frac{n (1 + n)}{2}$ ；
- 令数组 $nums$ 的求和值为 $sum$，由循环累加可得；
- 令数组 $sums$ 去重求和值为 $set$，由循环配合「哈希表/数组」累加可得。
最终答案为 (重复元素, 缺失元素) = (sum-set, tot-set) 。
代码；
[]class Solution { public int[] findErrorNums(int[] nums) { int n = nums.length; int[] cnts = new int[n + 1]; int tot = (1 + n) * n / 2; int sum = 0, set = 0; for (int x : nums) { sum += x; if (cnts[x] == 0) set += x; cnts[x] = 1; } return new int[]{sum - set, tot - set}; } }
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
桶排序
因为值的范围在 $[1, n]$，我们可以运用「桶排序」的思路，根据 $nums[i] = i + 1$ 的对应关系使用 $O(n)$ 的复杂度将每个数放在其应该落在的位置里。
然后线性扫描一遍排好序的数组，找到不符合 $nums[i] = i + 1$ 对应关系的位置，从而确定重复元素和缺失元素是哪个值。
代码：
[]class Solution { public int[] findErrorNums(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) { swap(nums, i, nums[i] - 1); } } int a = -1, b = -1; for (int i = 0; i < n; i++) { if (nums[i] != i + 1) { a = nums[i]; b = i == 0 ? 1 : nums[i - 1] + 1; } } return new int[]{a, b}; } void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 71430 | 166073 | 43.0% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 寻找重复数 | 中等 |
