当前位置:实例文章 » 其他实例» [文章]力扣热门100题之缺失的第一个正数【困难】

力扣热门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)。

其他信息

其他资源

Top