# 41 缺失的第一个正数
# 题目
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
# 题解
- 通过一次排序，然后一次遍历通过根据对比数进行比较来寻找最小的数
TIP
执行用时：84 ms, 在所有 JavaScript 提交中击败了 39.55% 的用户
内存消耗：37.4 MB, 在所有 JavaScript 提交中击败了 97.26% 的用户
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function(nums) {
let min = 1 // 最小的数，默认为 1
if(!nums.length) return min // 如果传空数组，则直接返回 1
let current = 1 // 用于对比的数，从 1 开始比较
let isNext = true // 用来记录是否是数组中没出现过的数
// 排序，按照从小到大的顺序排列
nums = nums.sort((a,b)=>a - b)
for (let i = 0, l = nums.length; i < l; i++) {
let item = nums[i] // 当前值
let prev = nums[i-1] || 0 // 上一个值，为了排除重复的值
// 只有当前的数大于 0 的时候，同时当前数不是重复数
if (item > 0 && prev !== item) {
/**
* 如果相同，则把*对比数 +1*
* 否则，说明找到了缺失的数
*/
if (item === current ) {
current++
} else {
min = current
isNext = false
break
}
}
}
// 如果 为 true，说明数组中没有最小的数
if(isNext) {
/**
* 这里比较是判断
* 当数组的最后一个数（也就是排序后的最大数）大于 0 时，则为 最大数 + 1，例：[1, 2] 为 3
* 否则，直接返回 1 即可，例： [-5] 为 1
*/
min = nums[nums.length - 1] > 0 ? nums[nums.length - 1] + 1 : min
}
return min
}
- 时间复杂度：
O(n)，一次通过 sort 排序，一次 for 循环。 - 空间复杂度：
O(1)，使用常数级别的几个变量。 - 最好的情况： 数组中前几位的值就出现了最小数，那么 for 循环直接 break 退出循环，节省了剩下遍历的时间。
- 最坏的情况： 也就是 isNext 为 true 的情况，需要遍历整个数组，数组中没有出现最小的数，那么就是 1 或者 最大数+1。
- 排序一次，然后遍历依次对比
TIP
执行用时：92 ms, 在所有 JavaScript 提交中击败了 22.94% 的用户
内存消耗：37.7 MB, 在所有 JavaScript 提交中击败了 90.85% 的用户
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function(nums) {
if(!nums.length) return 1
let min = 1
nums = nums.sort((a,b)=>a - b)
for(let i = 0, l = nums.length; i < l; i++) {
if(min === nums[i]) {
min++
}
}
return min
};
- 时间复杂度：
O(n)，一次通过 sort 排序，一次 for 循环。 - 空间复杂度：
O(1)，使用常数级别的几个变量。 - 最好的情况
- 最坏的情况
- 分别通过三次遍历来找到值，第一次遍历，把小于等于 0 的数和大于数组长度的数修改为 1，当然修改前还需要判断数组是否包含 1；第二次遍历，把数组里的值当做下标，修改对应的值为负数，重复的值需要先绝对值；第三次遍历寻找值是否大于 0，如果大于 0，说明没有出现过。最后如果都没有，则为数组的长度 +1。
TIP
执行用时：88 ms, 在所有 JavaScript 提交中击败了 30.62% 的用户
内存消耗：37.6 MB, 在所有 JavaScript 提交中击败了 93.60% 的用户
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function(nums) {
const {length: l} = nums
if(!nums.includes(1)) return 1 // 判断是否有 1，如果没有，则直接返回 1
for(let i=0;i<l;i++) {
// 依次把小于等于 0 的数和大于数组长度的数修改为 1
// 因为值肯定在 1 到 n.length 之间，超过的都不是目标值
let item = nums[i]
if(item <=0 || item > nums.length){
nums[i] = 1
}
}
for(let i=0;i<l;i++) {
// 依次把数值对应的下标修改为负数
let item = Math.abs(nums[i])
nums[item-1] = Math.abs(nums[item-1]) * -1
}
for(let i=0;i<l;i++) {
// 如果发现大于 0 的数，说明对应下标为最小的数
let item = nums[i]
if(item > 0) {
return i+1
}
}
// 如果都没有，则为数组的长度 +1
return l+1
};
- 时间复杂度：
O(n)，三次 for循环 - 空间复杂度：
O(1)，常数级别的空间 - 最好的情况： 当然是数组里没有出现 1，或者最小数在数组的前几位出现，这样遇到了直接返回值并退出函数，节省了剩下遍历的时间。
- 最坏的情况： 数组里没有出现最小数，值为数组的长度 +1，因为需要遍历所有的值。