Leetcode--缺失的最小的数（JavaScript解法）

ゞ浴缸里的玫瑰 2023-02-21 01:59 14阅读 0赞

#### 一、题目描述 ####

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

#### 二、示例 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70]

#### 三、解题思路 ####

其实刚开始的时候的思路也是有的，比如新建一个哈希表来处理，或者说我们先进行排序再使用二分法的方式来进行查找，但是题目要求的是空间复杂度为o(1)，所以我们可以在原来的数组上使用哈希，其实哈希的本质就是数组，我们不过是使用它不添加额外的空间。  
具体的思路是这样的：

我们可以将每个值放在第i-1位置上，比如1放在0上，2放在1上这样的思路，先进行遍历，依次判断进行交换，交换的条件就是：

*  值在0-len范围内
 *  nums\[i\]-1 和i值的比较
 *  nums\[nums\[i\]-1\] !== nums\[i\]-----交换之前看是否已经相等 相等的话不处理

这里需要注意的一点就是为什么不用if而是while ，我们交换之后，对交换后的i还要进行处理，如果用if的话就从i+1开始了，所以这里用while。  
最后将交换处理完的数组再进行一个遍历，寻找满足条件nums\[i\] !== i+1的i+1，如果没有的话直接返回 len+1就好。

#### 四、代码 ####

/** * @param {number[]} nums * @return {number} */
    
    var firstMissingPositive = function(nums) { 
        var len = nums.length;
        for(let i = 0 ; i < len ; i++){ 
            while(nums[i]>0 && nums[i]<len && nums[i]-1 !== i && nums[nums[i]-1] !== nums[i] ){ 
                swap(nums,nums[i]-1,i)
            }
        }
        for(let i = 0 ; i < len ; i++){ 
            if(nums[i] !== i+1){ 
                return i+1
            }
        }
        return len+1
    };
    function swap(nums,x,y){ 
            var temp = nums[x]
            nums[x] = nums[y]
            nums[y] = temp
    }

#### 五、结果 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200628112246492.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200628112201553.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4,size_16,color_FFFFFF,t_70