LeetCode热题100- 缺失的第一个正数【JavaScript讲解】

题目：

解题一：

如果不考虑时间复杂度和空间复杂度的话，我们最先想到的办法是先将该数组进行排序和去重，将最初的res结果值设置为1；将然后进行遍历，如果第一项不为1，则返回1，否则根据遍历res++；遍历结束后发现每一项都符合要求则返回res的最终值。代码如下：

代码一：

/*** @param {number[]} nums* @return {number}*/
var firstMissingPositive = function(nums) {nums = Array.from(new Set(nums));nums.sort((a,b)=>a-b);let res = 1;for(let i = 0; i < nums.length;i++){if(nums[i] > 0){if(nums[i] != res){return res;}res++;}}return res;
};

‌sort函数的时间复杂度为O(n log n)，空间复杂度为O(n)
‌new Set操作的时间复杂度是O(n)，空间复杂度也是O(n)‌
以上代码并没有满足题目要求的时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

解题二：

我们这次使用了一个Set（numSet）来存储数组中出现过的正数。首先，我们遍历原数组nums，将每个在1到n范围内的正数添加到Set中。然后，我们再次遍历从1到n的每个数字，检查它是否在Set中出现过。如果找到一个没有出现过的数字，我们就返回它作为缺失的第一个正整数。如果所有1到n的数字都出现过，我们则返回n+1。

代码二：

/*** @param {number[]} nums* @return {number}*/
var firstMissingPositive = function(nums) {let numSet = new Set();let n = nums.length;for(let i = 0; i < n;i++){if(nums[i] > 0 && nums[i] <= n){numSet.add(nums[i]);}}for(let i = 1; i <= n;i++){if(!numSet.has(i)){return i;}}return n + 1;
};

但是我们使用了一个额外的Set来存储出现过的数字，所以这里的空间复杂度为O(n)；时间复杂度是O(n)，因为我们只遍历了数组两次，并且Set的查找和插入操作都是O(1)的。

解题三：

将所有负数、0 都变为 N + 1，我们只需要考虑1-n的数字
遍历每个数，如果该数 |x| 属于[1,N]；把在 x-1 的位置的数加上一个负号
遍历完之后，如果全部数都是负数——答案就是 1+N，否则就是第一个正数的位置+1

代码三：

/*** @param {number[]} nums* @return {number}*/
var firstMissingPositive = function(nums) {let n = nums.length;for(let i = 0; i < n;i++){if(nums[i] <= 0) nums[i] = n + 1;}for(let i = 0; i < n;i++){let x = Math.abs(nums[i]);if(x >= 1 && x <= n){nums[x - 1] = nums[x - 1] < 0 ? nums[x - 1] : -nums[x - 1];}}for(let i = 0; i < n;i++){if(nums[i] >= 0) return i+1;}return n + 1;
};

此时就满足时间复杂度为o(n),空间复杂度为常数的代码了。此思路借鉴于力扣博主okkjoo，具体地址点击此处跳转。

当博主问朋友解决方案的时候，他二话不说的告诉我“用桶排啊！！”，于是，、、、、这篇文章到这里没有结束，，明天博主会尽快将桶排的方法补充上去，也欢迎小伙伴们在评论区留下你们的答案哦~~~~~