leetcode41-缺失的第一个正数

leetcode 41

思路

最小正整数的范围： 如果数组的长度是 n，那么缺失的最小正整数一定是从 1 到 n+1 之间的某个数字。因为数组如果包含了所有从 1 到 n 的数字，那么缺失的最小正整数就是 n + 1

• 例如，如果数组 [1, 2, 3]，缺失的最小正整数是 4；如果数组 [3, -1, 2, 1]，缺失的最小正整数是 4

所以我们可以考虑到从1到n+1之间的每个数去遍历，看看数组中是否出现这个数，只要数组中没出现过，那说明当前这个数是最小正整数
如果通过数组的includes方法来查找，时间复杂度是O(n2)，题目要求使用O(n)的复杂度来完成本题
那么可以牺牲空间来节省时间，我们知道set够在常数时间 O(1) 内检查某个数字是否存在

• 从 1 开始，逐一检查 Set 中是否存在每个正整数。如果某个整数不存在于 Set 中，则返回它，因为它就是缺失的最小正整数

实现

var firstMissingPositive = function (nums) {const len = nums.length;const set = new Set(nums);for(let i = 1;i <= len+1;i++){if(!set.has(i)){return i}}
};