Appearance
41. 缺失的第一个正数
题目描述
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
**输入：**nums = [1,2,0] **输出：**3 **解释：**范围 [1,2] 中的数字都在数组中。
示例 2：
**输入：**nums = [3,4,-1,1] **输出：**2 **解释：**1 在数组中，但 2 没有。
示例 3：
**输入：**nums = [7,8,9,11,12] **输出：**1 **解释：**最小的正数 1 没有出现。
提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
难度： Hard
题解代码
javascript
/**
* @param {number[]} nums
* @return {number}
*/
// const firstMissingPositive = nums => {
// if (!nums.length || (nums.length === 1 && nums[0] !== 1)) return 1
// // 中心思想是先采用冒泡排序 在判断排序后的两个元素的条件
// // 分支逻辑是真尼玛多
// for (let i = 0; i < nums.length; i++) {
// let min = nums[i]
// for (let j = i + 1; j < nums.length; j++) {
// if (nums[j] < min) {
// let temp = nums[i]
// min = nums[j]
// nums[i] = nums[j]
// nums[j] = temp
// }
// }
// if (nums[0] > 1) return 1
// // 第二次选择排序， 不包括只有两个元素的情况
// if ((i >= 1 && nums[i - 1] < 0 && nums[i] > 1)) {
// return 1
// }
// if (i >= 1 && nums[i - 1] >= 0 && nums[i] - nums [i - 1] > 1) {
// if (i === 1 && nums[0] > 1) {
// return 1
// }
// if (nums[i - 2] && nums[i - 2] < 1 && nums[i - 1] > 1) {
// return 1
// }
// return nums[i - 1] + 1
// }
// }
// if (nums[0] > 1) return 1
// if (nums[1] > 1 && nums[0] < 1) return 1
// return nums[nums.length - 1] > 0 ? nums[nums.length - 1] + 1 : 1
// };
const firstMissingPositive = nums => {
if (!nums.length) return 1
const set = new Set([...nums])
let ret = 1
for (let i = 1; i < nums.length + 1; i++) {
if (!set.has(i)) {
return i
}
ret = i
}
return ret + 1
}