LeetCode刷题Java版041.缺失的第一个整数

作者：沉默王二
发布时间：2022-09-14T19:23:17.244+0800

---

041.缺失的第一个整数

题意

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

难度

困难

示例

输入：nums = [1,2,0]

输入：nums = [3,4,-1,1]输出：2

分析

本题如果没有 只使用常数级别额外空间 这个限制条件的话，非常容易解决，只需要额外开一个哈希表来存储使用过的数字就可以了。

但是很遗憾，有这个限制条件。

不过没关系，我们先来看看题目要求我们做的事情——找出没有在nums[]出现的最小正整数。

我们约定一下，n为nums[]数组的长度。

那是不是有这样一种情况，就是1 - n中的每个整数，都在nums[]中出现过一次。

即——nums[]是一个n的排列。

这样子的话答案肯定就是n + 1！

因为1 - n全都出现过了，只有n + 1没有出现过。

也就是说——除了1-n之外的数字，即小于等于0的数和大于n的数字，对我们的 ”帮助“ 其实是一样的，所以我们可以把他们变成同一个数字，这里先暂定为n + 1。

再来看看我们手中现在有的东西——nums[]（只剩下正整数了）以及常数级别的额外空间。

因为我们把所有的0和负数都转化为了n + 1。

想一想哈希表——就是利用0和1两种状态来表示这个数字是否存在的。

那么我们是不是也可以找找nums[]能不能有相应的两种状态呢？

有！那就是正数和负数两个状态，因为我们先前已经把所有的负数变成正数了，所以这就是新的哈希表的状态。利用nums[x]的正负，来表示x是否存在。正数表示不存在，负数表示存在。

所以这时候，我们的哈希表就浮现出来了。

如果x > n呢？不着急，直接忽略它就好了，因为它不可能成为答案，跟上面去除负数的原理是一样的。

最后再扫描一遍nums[]，第一个正整数，就是答案！

最后注意一下，因为nums[]只有0-(n - 1)，所以标记的时候记得减一即可。

class Solution {

        for(int i = 0;i < nums.length;i++){            if(nums[i] <= 0)                nums[i] = nums.length + 1;        }        for(int i = 0;i < nums.length;i++){            if(nums[i] > nums.length)                continue;            nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);        }        int ans = nums.length + 1;        for(int i = 0;i < nums.length;i++)            if(nums[i] > 0){                ans = i + 1;                break;            }        return ans;    }}

因为只扫描了三遍数组，所以时间复杂度为。运行效率也不负所望。

总结

当题目限制我们在一定的条件下的时候，一定要想尽一切办法利用可以利用的资源，这也是这道困难题给我们的启发，本来如果是没有限制的话，就是一道简单题，只需要用哈希表记录即可，但是限制了之后，就需要我们利用眼前的东西，来实现平时简单模式下的功能。

力扣链接：https://leetcode.cn/problems/first-missing-positive/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 790 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

041.缺失的第一个整数

题意

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

难度

困难

示例

输入：nums = [1,2,0]

输入：nums = [3,4,-1,1]输出：2

分析

本题如果没有 只使用常数级别额外空间 这个限制条件的话，非常容易解决，只需要额外开一个哈希表来存储使用过的数字就可以了。

但是很遗憾，有这个限制条件。

不过没关系，我们先来看看题目要求我们做的事情——找出没有在nums[]出现的最小正整数。

我们约定一下，n为nums[]数组的长度。

那是不是有这样一种情况，就是1 - n中的每个整数，都在nums[]中出现过一次。

即——nums[]是一个n的排列。

这样子的话答案肯定就是n + 1！

因为1 - n全都出现过了，只有n + 1没有出现过。

也就是说——除了1-n之外的数字，即小于等于0的数和大于n的数字，对我们的 ”帮助“ 其实是一样的，所以我们可以把他们变成同一个数字，这里先暂定为n + 1。

再来看看我们手中现在有的东西——nums[]（只剩下正整数了）以及常数级别的额外空间。

因为我们把所有的0和负数都转化为了n + 1。

想一想哈希表——就是利用0和1两种状态来表示这个数字是否存在的。

那么我们是不是也可以找找nums[]能不能有相应的两种状态呢？

有！那就是正数和负数两个状态，因为我们先前已经把所有的负数变成正数了，所以这就是新的哈希表的状态。利用nums[x]的正负，来表示x是否存在。正数表示不存在，负数表示存在。

所以这时候，我们的哈希表就浮现出来了。

如果x > n呢？不着急，直接忽略它就好了，因为它不可能成为答案，跟上面去除负数的原理是一样的。

最后再扫描一遍nums[]，第一个正整数，就是答案！

最后注意一下，因为nums[]只有0-(n - 1)，所以标记的时候记得减一即可。

class Solution {

        for(int i = 0;i < nums.length;i++){            if(nums[i] <= 0)                nums[i] = nums.length + 1;        }        for(int i = 0;i < nums.length;i++){            if(nums[i] > nums.length)                continue;            nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);        }        int ans = nums.length + 1;        for(int i = 0;i < nums.length;i++)            if(nums[i] > 0){                ans = i + 1;                break;            }        return ans;    }}

因为只扫描了三遍数组，所以时间复杂度为。运行效率也不负所望。

总结

当题目限制我们在一定的条件下的时候，一定要想尽一切办法利用可以利用的资源，这也是这道困难题给我们的启发，本来如果是没有限制的话，就是一道简单题，只需要用哈希表记录即可，但是限制了之后，就需要我们利用眼前的东西，来实现平时简单模式下的功能。

力扣链接：https://leetcode.cn/problems/first-missing-positive/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 790 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

041.缺失的第一个整数

题意

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

难度

困难

示例

输入：nums = [1,2,0]

输入：nums = [3,4,-1,1]输出：2

分析

本题如果没有 只使用常数级别额外空间 这个限制条件的话，非常容易解决，只需要额外开一个哈希表来存储使用过的数字就可以了。

但是很遗憾，有这个限制条件。

不过没关系，我们先来看看题目要求我们做的事情——找出没有在nums[]出现的最小正整数。

我们约定一下，n为nums[]数组的长度。

那是不是有这样一种情况，就是1 - n中的每个整数，都在nums[]中出现过一次。

即——nums[]是一个n的排列。

这样子的话答案肯定就是n + 1！

因为1 - n全都出现过了，只有n + 1没有出现过。

也就是说——除了1-n之外的数字，即小于等于0的数和大于n的数字，对我们的 ”帮助“ 其实是一样的，所以我们可以把他们变成同一个数字，这里先暂定为n + 1。

再来看看我们手中现在有的东西——nums[]（只剩下正整数了）以及常数级别的额外空间。

因为我们把所有的0和负数都转化为了n + 1。

想一想哈希表——就是利用0和1两种状态来表示这个数字是否存在的。

那么我们是不是也可以找找nums[]能不能有相应的两种状态呢？

有！那就是正数和负数两个状态，因为我们先前已经把所有的负数变成正数了，所以这就是新的哈希表的状态。利用nums[x]的正负，来表示x是否存在。正数表示不存在，负数表示存在。

所以这时候，我们的哈希表就浮现出来了。

如果x > n呢？不着急，直接忽略它就好了，因为它不可能成为答案，跟上面去除负数的原理是一样的。

最后再扫描一遍nums[]，第一个正整数，就是答案！

最后注意一下，因为nums[]只有0-(n - 1)，所以标记的时候记得减一即可。

class Solution {

        for(int i = 0;i < nums.length;i++){            if(nums[i] <= 0)                nums[i] = nums.length + 1;        }        for(int i = 0;i < nums.length;i++){            if(nums[i] > nums.length)                continue;            nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);        }        int ans = nums.length + 1;        for(int i = 0;i < nums.length;i++)            if(nums[i] > 0){                ans = i + 1;                break;            }        return ans;    }}

因为只扫描了三遍数组，所以时间复杂度为。运行效率也不负所望。

总结

当题目限制我们在一定的条件下的时候，一定要想尽一切办法利用可以利用的资源，这也是这道困难题给我们的启发，本来如果是没有限制的话，就是一道简单题，只需要用哈希表记录即可，但是限制了之后，就需要我们利用眼前的东西，来实现平时简单模式下的功能。

力扣链接：https://leetcode.cn/problems/first-missing-positive/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 790 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412