如何寻找缺失和重复的元素
通知：数据结构精品课 和 递归算法专题课 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》 出版，签名版限时半价！另外，建议你在我的 网站 学习文章，体验更好。
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 645. Set Mismatch | 645. 错误的集合 | 🟢 |
-----------
今天就聊一道很看起来简单却十分巧妙的问题，寻找缺失和重复的元素。之前的一篇文章 常用的位操作 中也写过类似的问题，不过这次的和上次的问题使用的技巧不同。
这是力扣第 645 题「错误的集合」，我来描述一下这个题目：
给一个长度为 N 的数组 nums，其中本来装着 [1..N] 这 N 个元素，无序。但是现在出现了一些错误，nums 中的一个元素出现了重复，也就同时导致了另一个元素的缺失。请你写一个算法，找到 nums 中的重复元素和缺失元素的值。
// 返回两个数字，分别是 {dup, missing}
int[] findErrorNums(int[] nums);比如说输入：nums = [1,2,2,4]，算法返回 [2,3]。
其实很容易解决这个问题，先遍历一次数组，用一个哈希表记录每个数字出现的次数，然后遍历一次 [1..N]，看看那个元素重复出现，那个元素没有出现，就 OK 了。
但问题是，这个常规解法需要一个哈希表，也就是 O(N) 的空间复杂度。你看题目给的条件那么巧，在 [1..N] 的几个数字中恰好有一个重复，一个缺失，事出反常必有妖，对吧。
O(N) 的时间复杂度遍历数组是无法避免的，所以我们可以想想办法如何降低空间复杂度，是否可以在 O(1) 的空间复杂度之下找到重复和缺失的元素呢？
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：
＿＿＿＿＿＿＿＿＿＿＿＿＿
本文为会员内容，请扫码关注公众号或 点这里 查看：
====其他语言代码====
java
zhuli提供的Java代码：
class Solution {
public int[] findErrorNums(int[] nums) {
int n = nums.length;
int dup = -1;
for (int i = 0; i < n; i++) {
// 元素是从 1 开始的
int index = Math.abs(nums[i]) - 1;
// nums[index] 小于 0 则说明重复访问
if (nums[index] < 0)
dup = Math.abs(nums[i]);
else
nums[index] *= -1;
}
int missing = -1;
for (int i = 0; i < n; i++)
// nums[i] 大于 0 则说明没有访问
if (nums[i] > 0)
// 将索引转换成元素
missing = i + 1;
return new int[]{dup, missing};
}
}javascript
/**
* @param {number[]} nums
* @return {number[]}
*/
var findErrorNums = function (nums) {
let n = nums.length;
let dup = -1;
for (let i = 0; i < n; i++) {
// 现在的元素是从1开始的
let index = Math.abs(nums[i]) - 1;
if (nums[index] < 0) {
dup = Math.abs(nums[i]);
} else {
nums[index] *= -1;
}
}
let missing = -1;
for (let i = 0; i < n; i++) {
if (nums[i] > 0) {
// 将索引转换成元素
missing = i + 1;
}
}
return [dup, missing]
};