力扣热门100题之缺失的第一个正数【困难】
发布人：shili8
发布时间：2025-03-15 13:23
阅读次数：0
**力扣热门100题之缺失的第一个正数**
**难度:**困难**描述:**
给定一个长度为 n 的整数数组 nums，其中可能有重复元素。请找到缺失的第一个正数。
**示例1:**
输入:nums = [1,2,0]
输出:4**示例2:**
输入:nums = [3,4,-1,1]
输出:2**示例3:**
输入:nums = [-1,-1000,3,99]
输出:1**限制条件:**
-1 <= n <=10^5- -10^5 <= nums[i] <=10^5**思路和解法:**
本题要求找到缺失的第一个正数。我们可以使用哈希表来存储出现过的数字，然后遍历从1 到 n 的范围内，找出哪个数字没有在哈希表中。
class Solution: def firstMissingPositive(self, nums: List[int]) -> int: # 使用集合来存储出现过的数字 num_set = set(nums) # 遍历从1 到 n 的范围内，找出哪个数字没有在哈希表中 for i in range(1, len(nums) +2): if i not in num_set: return i # 如果所有数字都出现过，则返回 n +1 return len(nums) +1
**时间复杂度:** O(n)
**空间复杂度:** O(n)
**注意:**
- 本题要求找到缺失的第一个正数，因此我们需要从1 开始遍历。
- 如果所有数字都出现过，则返回 n +1。
**其他解法:**
- **排序后遍历**:首先将数组排序，然后遍历从1 到 n 的范围内，找出哪个数字没有在数组中。时间复杂度为 O(n log n)。
- **位图**:使用位图来存储出现过的数字，然后遍历从1 到 n 的范围内，找出哪个数字没有在位图中。时间复杂度为 O(n)。
**总结:**
本题要求找到缺失的第一个正数。我们可以使用哈希表或位图来存储出现过的数字，然后遍历从1 到 n 的范围内，找出哪个数字没有在哈希表中或位图中。时间复杂度为 O(n)。
粤公网安备 44011102002787号