LeeCode题库第四十一题

41.缺失的第一个整数 

项目场景：

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

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

示例 1：

输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。

提示：

1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1

---

问题描述

        求缺失的第一个整数，如果nums[i]对应的元素小于0或者大于n将此时的值置为0因为此时这个元素肯定不是缺失的正数。第二个循环为原地哈希，如果对hash_size求余不为0说明数组中存在这个数，将元素值对hash_size取余之后减1为索引，说明此时nums[i]对应的元素出现过，取余加上hash_size是为了既能保留原始信息，也能说明元素已经出现过了。最后遍历数组，如果条件不符合则返回i+1为缺失的整数，因为i为索引。

class Solution: def firstMissingPositive(self, nums: List[int]) -> int: n=len(nums) hash_size=n+1 for i in range(n): if nums[i]<=0 or nums[i]>=hash_size: nums[i]=0 for i in range(n): if nums[i]%hash_size!=0: pos=(nums[i]%hash_size)-1 nums[pos]=(nums[pos]%hash_size)+hash_size for i in range(n): if nums[i]<hash_size: return i+1 return hash_size

        以上为本篇文章的全部内容，感谢你抽出宝贵的时间阅读这篇文章。如果你有任何疑问或建议，欢迎在评论区留言，我们一起交流进步。愿你的代码之路越走越顺，生活充满阳光！