企业官网建设流程全解析

给你一个未排序的整数数组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. 范围确定：缺失的最小正整数一定在[1, n+1]范围内（n 为数组长度）。例如数组长度为 3，若 1、2、3 都存在则返回 4，否则返回缺失的最小数。
2. 过滤无效值：将数组中所有≤0 或 > n 的数替换为n+1（这些数不可能是目标，替换后不干扰后续标记）。
3. 标记存在的数：遍历数组，对每个元素x（取绝对值），若x ≤ n，则将数组第x-1位标记为负数（表示x这个数存在）。
4. 查找缺失值：遍历数组，第一个正数的位置i+1就是缺失的最小正整数；若全为负数，说明 1~n 都存在，返回n+1。

示例验证

示例 1：输入nums = [1,2,0]

1. 过滤无效值：0 替换为 4 →[1,2,4]；
2. 标记存在的数：
   • x=1 → nums[0] = -1；
   • x=2 → nums[1] = -2；
   • x=4（>3）→ 不处理；数组变为[-1,-2,4]；
3. 遍历找正数：索引 2 是第一个正数，返回2+1=3（符合预期）。

示例 2：输入nums = [3,4,-1,1]

1. 过滤无效值：-1 替换为 5，4 替换为 5 →[3,5,5,1]；
2. 标记存在的数：
   • x=3 → nums[2] = -5；
   • x=5（>4）→ 不处理；
   • x=5（>4）→ 不处理；
   • x=1 → nums [0] = -3；数组变为[-3,5,-5,1]；
3. 遍历找正数：索引 1 是第一个正数，返回1+1=2（符合预期）。

示例 3：输入nums = [7,8,9,11,12]

1. 过滤无效值：所有数 > 5，替换为 6 →[6,6,6,6,6]；
2. 标记存在的数：所有 x=6（>5）→ 不处理，数组仍为[6,6,6,6,6]；
3. 遍历找正数：索引 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等编程挑战。