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，具体地址点击此处跳转。

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