41。缺失的第一个正数给定一个未排序的整数数组，请找到其中没有出现的最小正整数。示例1：输入：[1,2,0]输出：3示例2：输入：[3,4,-1,1]输出：2示例3：输入：[7,8,9,11,12]输出:1提示：您的算法应该具有O(n)的时间复杂度，并且只使用恒定级别的额外空间。解题思路：交流因为题目要求【算法的时间复杂度应该是O(n)，只能使用常量级的额外空间】。如果没有这个限制，可以使用哈希表的方法：将数组元素存入哈希表，从头开始遍历，判断是否在哈希表中（但这种方法的时间复杂度为O(n),但是空间复杂度也是O(n),不满足前提)但是仔细看题会发现题给的数组是没有排序的。那么如果恢复给定的数组，此时可以通过遍历和校验找到丢失的正数。在给定的数组中，我们要找的整数一定在[1,n+1]区间内（n代表数组的长度）。但是n+1就不是必须的了，因为前面n个数都不满足的时候，要求自然就是n+1了。我们看例子2：输入：[3,4,-1,1]输出：2在这个例子中，我们还原它，那么最终的数组是这样的：[1,-1,3,4]，所以我们可以发现数组中缺失的数字是数字2。那么现在的问题就是如何恢复。总体思路是：将1放在索引0处，将2放在索引1处，依此类推。也就是说，设当前遍历的元素为a，也就是说a=nums[i]，如果a落在[1,n]中，按照上面的思路，那么a应该落在索引为a-1。这时候交换nums[i]和nums[a-1]，那么a就会落在正确的位置上。但是，如果交换位置后的元素还在[1,n]范围内，则需要继续交换操作，直到a不再落在[1,n]内。具体过程如下图所示：这里需要注意防止陷入死循环。如果a已经在正确的位置，则上述方法将始终交换。所以这里要注意，当元素出现在正确的位置时，不需要交换跳转，直接进入下一个元素。具体代码实现如下。代码实现类解决方案：deffirstMissingPositive(self,nums:List[int])->int:length=len(nums)foriinrange(length):#这里判断元素是否落在[1,n]内，判断是否落在正确位置#注意：防止进入死循环，当元素刚落在正确位置时，直接跳过，判断下一个元素while1<=nums[i]<=lengthandnums[i]!=nums[nums[i]-1]:#交换nums[nums[i]-1],nums[i]=nums[i],nums[nums[i]-1]#恢复后的元素数组到正确的位置，#再次遍历，当有元素不在正确的位置时，第一个缺失的正数找，直接返回foriinrange(length):ifnums[i]!=i+1:returni+1#如果元素都在正确的位置，那么缺失就是n+1(length+1)returnlength+1实现结果汇总因为给定的数组没有排序，而我们知道所需的缺失正数，然后will数组恢复到正确的位置，那么遍历的时候就会知道哪个正数不在正确的位置，也就是缺失的正数根据题意，我们知道我们是的正数寻找必须落在[1,n+1]（n代表数组的长度）这个区间内。但是n+1不是必须的，因为如果前面的都在正确的位置，那么缺的就是n+1。如何恢复：根据上面，大意是：1应该落在index0的位置，2应该落在index1的位置，以此类推。假设当前元素是a（为了便于理解，设a=nums[i]），如果a落在区间[1,n]，那么a应该落在索引为a-1的位置。然后交换位置，即交换nums[a-1]与a（代入a=nums[i]，即交换nums[nums[i]-1]与nums[i]），交换后，a可能仍然落在[1,n]中，直到a不再在这个区间内。这里注意：不要陷入死循环。上述前提是a落在[1,n]区间。要把a放在正确的位置，需要注意以下几点。如果a落在正确的位置，交换将无限期地继续下去。因此，当a落在正确位置时，直接跳过，遍历下一个元素。文章是原创的，我觉得写的不错。欢迎关注和点赞。微信公众号《书所集录》同步更新，也欢迎大家关注点赞。
