作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
LeetCode题目41“缺失的第一个正数”要求在未排序的整数数组中找出最小的未出现的正整数。本文将详细介绍三种解决这一问题的方法，包括解题思路、详细的代码实现以及算法分析。
题目描述
输入：一个未排序的整数数组 nums。
输出：未在数组中出现的最小正整数。
示例：
输入: [1,2,0] 输出: 3
输入: [3,4,-1,1] 输出: 2
输入: [7,8,9,11,12] 输出: 1
方法一：索引作为哈希键
解题步骤
- 处理负数和零：由于我们只关心正数，可以先将所有非正整数替换为一个大于数组长度的值（例如
n+1，其中n是数组长度）。 - 利用索引标记：遍历数组，使用数组索引作为哈希键来标记存在的数字。具体操作是，对于每个数字
x，如果1 <= x <= n，则将索引x-1的位置的数字设置为负数。 - 寻找结果：再次遍历数组，第一个索引位置
i使得nums[i] > 0的i + 1就是缺失的最小正数。
代码示例
def firstMissingPositive(nums): n = len(nums) # 将所有的负数和零替换为n+1，n+1是一个不可能出现在合法输出中的数字 for i in range(n): if nums[i] <= 0: nums[i] = n + 1 # 使用数组索引作为哈希键，通过置负标记存在的数字 for i in range(n): num = abs(nums[i]) if num <= n: nums[num - 1] = -abs(nums[num - 1]) # 寻找第一个大于0的索引位置，即是缺失的最小正数 for i in range(n): if nums[i]> 0: return i + 1 # 如果数组中包含了1到n的所有数字，则缺失的第一个正数是n+1 return n + 1 # 示例调用 print(firstMissingPositive([1, 2, 0])) # 输出: 3 print(firstMissingPositive([3, 4, -1, 1])) # 输出: 2 print(firstMissingPositive([7, 8, 9, 11, 12])) # 输出: 1
算法分析
- 时间复杂度：O(N)，其中 N 是数组长度。算法涉及几个线性扫描，每个扫描的时间复杂度都是O(N)。
- 空间复杂度：O(1)。除了输入数组外，没有使用额外的空间，所有操作均在原数组上进行。
方法二：排序后线性扫描
解题步骤
- 排序数组：首先对数组进行排序。
- 线性扫描：遍历排序后的数组，查找第一个缺失的最小正数。
代码示例
def firstMissingPositive(nums): nums.sort() target = 1 for num in nums: if num == target: target += 1 return target # 示例调用 print(firstMissingPositive([1, 2, 0])) # 输出: 3 print(firstMissingPositive([3, 4, -1, 1])) # 输出: 2 print(firstMissingPositive([7, 8, 9, 11, 12])) # 输出: 1
算法分析
- 时间复杂度：O(N log N)，主要时间开销来源于排序。
- 空间复杂度：O(1) 或 O(N)，这取决于使用的排序算法。
方法三：使用哈希表
解题步骤
- 使用哈希表存储：将所有正数存储在哈希表中。
- 寻找最小正数：从 1 开始递增寻找不在哈希表中的最小正数。
代码示例
def firstMissingPositive(nums): num_set = set(nums) target = 1 while target in num_set: target += 1 return target # 示例调用 print(firstMissingPositive([1, 2, 0])) # 输出: 3 print(firstMissingPositive([3, 4, -1, 1])) # 输出: 2 print(firstMissingPositive([7, 8, 9, 11, 12])) # 输出: 1
算法分析
- 时间复杂度：O(N)，虽然使用了哈希表，但构建哈希表和查询的总时间仍是线性的。
- 空间复杂度：O(N)，需要额外的空间来存储哈希表。
总结
为了直观地比较解决LeetCode题目41 "缺失的第一个正数"的三种方法，下面的表格将展示它们在不同技术维度的性能和特点，包括时间复杂度、空间复杂度以及各自的优势和劣势。
| 特征 | 方法一：索引作为哈希键 | 方法二：排序后线性扫描 | 方法三：使用哈希表 |
| 时间复杂度 | O(N) | O(N log N) | O(N) |
| 空间复杂度 | O(1) | O(1) 或 O(N) | O(N) |
| 优势 | - 不使用额外空间 - 快速且高效 - 直接在原数组上操作，不需要额外的数据结构 |
- 实现简单 - 直观易理解 - 适用于不限制时间复杂度的场景 |
- 实现简单 - 查找速度快 - 直接使用Python内置数据结构 |
| 劣势 | - 算法理解相对复杂 - 需要修改原数组作为标记 |
- 时间复杂度较高，尤其是在数据量大时 - 空间复杂度依赖于排序算法 |
- 空间开销大 - 需要额外空间存储所有正数 |
| 适用场景 | - 数据量大且对空间有严格限制时 - 需要在原地解决问题时 |
- 数据预处理和排序成本低时 - 对算法执行时间要求不严格时 |
- 空间充足时 - 需要快速实现和简洁代码时 |
欢迎关注微信公众号 数据分析螺丝钉
