【LeetCode刷题】缺失的第一个正数
给你一个未排序的整数数组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 <=-231 <= nums[i] <=
解题思路
要在 O (n) 时间复杂度和常数级额外空间内解决问题，核心思路是原地哈希（标记）：
- 范围确定：缺失的最小正整数一定在
[1, n+1]范围内（n 为数组长度）。例如数组长度为 3，若 1、2、3 都存在则返回 4，否则返回缺失的最小数。 - 过滤无效值：将数组中所有≤0 或 > n 的数替换为
n+1（这些数不可能是目标，替换后不干扰后续标记）。 - 标记存在的数：遍历数组，对每个元素
x（取绝对值），若x ≤ n，则将数组第x-1位标记为负数（表示x这个数存在）。 - 查找缺失值：遍历数组，第一个正数的位置
i+1就是缺失的最小正整数；若全为负数，说明 1~n 都存在，返回n+1。
示例验证
示例 1：输入nums = [1,2,0]
- 过滤无效值：0 替换为 4 →
[1,2,4]； - 标记存在的数：
- x=1 → nums[0] = -1；
- x=2 → nums[1] = -2；
- x=4（>3）→ 不处理；数组变为
[-1,-2,4]；
- 遍历找正数：索引 2 是第一个正数，返回
2+1=3（符合预期）。
示例 2：输入nums = [3,4,-1,1]
- 过滤无效值：-1 替换为 5，4 替换为 5 →
[3,5,5,1]； - 标记存在的数：
- x=3 → nums[2] = -5；
- x=5（>4）→ 不处理；
- x=5（>4）→ 不处理；
- x=1 → nums [0] = -3；数组变为
[-3,5,-5,1]；
- 遍历找正数：索引 1 是第一个正数，返回
1+1=2（符合预期）。
示例 3：输入nums = [7,8,9,11,12]
- 过滤无效值：所有数 > 5，替换为 6 →
[6,6,6,6,6]； - 标记存在的数：所有 x=6（>5）→ 不处理，数组仍为
[6,6,6,6,6]； - 遍历找正数：索引 0 是第一个正数，返回
0+1=1（符合预期）。
核心优势
- 时间复杂度 O (n)：仅三次线性遍历，无嵌套操作；
- 空间复杂度 O (1)：仅使用常数级临时变量，原地修改数组；
- 鲁棒性：处理了负数、重复值、超大数等边界场景，适配题目 10⁵级别的数组长度。
Python代码：
from typing import List class Solution: def firstMissingPositive(self, nums: List[int]) -> int: n = len(nums) # 过滤无效值 for i in range(n): if nums[i] <= 0 or nums[i] > n: nums[i] = n + 1 # 标记存在的数 for i in range(n): x = abs(nums[i]) if x <= n: nums[x - 1] = -abs(nums[x - 1]) # 查找缺失值 for i in range(n): if nums[i] > 0: return i + 1 return n + 1 # 测试用例 if __name__ == "__main__": solution = Solution() # 示例1 nums1 = [1,2,0] print(f"示例1输入: {nums1}") print(f"示例1输出: {solution.firstMissingPositive(nums1)}") # 示例2 nums2 = [3,4,-1,1] print(f"示例2输入: {nums2}") print(f"示例2输出: {solution.firstMissingPositive(nums2)}") # 示例3 nums3 = [7,8,9,11,12] print(f"示例3输入: {nums3}") print(f"示例3输出: {solution.firstMissingPositive(nums3)}") # 边界用例：1~n都存在 nums4 = [1,2,3,4] print(f"示例4输入: {nums4}") print(f"示例4输出: {solution.firstMissingPositive(nums4)}") # 边界用例：空值/重复值 nums5 = [2,2,2] print(f"示例5输入: {nums5}") print(f"示例5输出: {solution.firstMissingPositive(nums5)}")LeetCode提交代码：
from typing import List class Solution: def firstMissingPositive(self, nums: List[int]) -> int: n = len(nums) # 步骤1：过滤无效值（≤0 或 >n的数替换为n+1，不干扰后续标记） for i in range(n): if nums[i] <= 0 or nums[i] > n: nums[i] = n + 1 # 步骤2：标记存在的正整数（用负数标记，表示对应数存在） for i in range(n): x = abs(nums[i]) # 取绝对值，避免已标记的负数干扰 if x <= n: # 仅处理1~n范围内的数 nums[x - 1] = -abs(nums[x - 1]) # 标记为负数（重复标记不影响） # 步骤3：查找第一个未标记的位置（正数），返回i+1 for i in range(n): if nums[i] > 0: return i + 1 # 所有1~n都存在，返回n+1 return n + 1程序运行结果如下：
示例1输入: [1, 2, 0] 示例1输出: 3 示例2输入: [3, 4, -1, 1] 示例2输出: 2 示例3输入: [7, 8, 9, 11, 12] 示例3输出: 1 示例4输入: [1, 2, 3, 4] 示例4输出: 5 示例5输入: [2, 2, 2] 示例5输出: 1总结
本文提出了一种在O(n)时间复杂度和常数空间内寻找数组中缺失最小正整数的算法。核心思路是通过原地哈希标记：首先过滤无效值（≤0或>n的数），然后利用数组索引标记存在的正整数（1~n），最后扫描数组找到第一个未被标记的位置。该方法高效处理了各种边界情况（负数、重复值、超大数等），并通过三个线性遍历实现最优复杂度。Python实现验证了算法的正确性，适用于LeetCode等编程挑战。