# 645 错误的集合
# 题目
集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
注意:
给定数组的长度范围是 [2, 10000]。 给定的数组是无序的。
# 题解
- 首先排序，然后遍历一次，使用 set 数据结结构储存每次出现的值，当已经储存过了，说明遇到重复的值；寻找缺失的值是使用一个基于 1 的起始值，因为值默认是从 1 开始的，遍历的过程中，如果新添加值的情况下，那么就判断该值是否等于 count，如果等于说明不是缺失的值，那么就给 count +1。最后，如果都没有，那么缺失的值就是数组的长度。
TIP
执行用时：156 ms, 在所有 JavaScript 提交中击败了 20.88% 的用户
内存消耗：45.8 MB, 在所有 JavaScript 提交中击败了 14.47% 的用户
/**
* @param {number[]} nums
* @return {number[]}
*/
var findErrorNums = function(nums) {
let set = new Set();
let repeat; // 重复的值
let missing = nums.length; // 默认设置为数组的长度
let count = 1; // 对比值
nums.sort((a, b) => a - b); // 排序
for (let i = 0; i < nums.length; i++) {
const item = nums[i]; // 当前值
if (set.has(item)) {
// 如果已经存在过了，说明找到重复的值了
repeat = item;
} else {
set.add(item); // 添加新值
if (item === count) {
// 不是缺失的值，对比值 +1
count++;
} else {
// 找到缺失的值了
missing = count;
}
}
}
return [repeat, missing];
}
- 这个解法是上面的改良版，这里使用数组进行储存值，查找的时候就不用遍历一次，直接使用下标寻找值(
O(1))。
TIP
执行用时：124 ms, 在所有 JavaScript 提交中击败了 35.53% 的用户
内存消耗：42.9 MB, 在所有 JavaScript 提交中击败了 26.32% 的用户
/**
* @param {number[]} nums
* @return {number[]}
*/
var findErrorNums = function(nums) {
let set = [] // 使用数组
let repeat;
let missing = nums.length;
let count = 1;
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
const item = nums[i];
if(set[item] != undefined) {
// 如果不为 undefined，说明已经储存过了，
// 则找到重复的值
repeat = item
} else {
// 设置新值
set[item] = item
if(item === count) {
count++
} else {
missing = count
}
}
}
return [repeat, missing];
}
- 这次不用排序，使用双循环进行查找，第一次循环，设置数组里面对应的值，这里从 1 开始设置。第二次循环，寻找缺失的数字。
TIP
执行用时：92 ms, 在所有 JavaScript 提交中击败了 75.82% 的用户
内存消耗：43 MB, 在所有 JavaScript 提交中击败了 25.00% 的用户
/**
* @param {number[]} nums
* @return {number[]}
*/
var findErrorNums = function(nums) {
let set = []
let repeat;
let missing = nums.length;
const {length: l} = nums
for(let i=1;i<=l;i++) {
let item = nums[i-1]
if(set[item] != undefined) {
repeat = item
}
set[item] = item
}
for(let i=1;i<=l;i++) {
if(set[i] == undefined) {
missing = i
break
}
}
return [repeat, missing];
}