LeetCode第41题_缺失的第一个正数_leetcode 41

LeetCode 第41题：缺失的第一个正数

题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

难度

困难

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：nums = [1,2,0]
输出：3
解释：数字 1 和 2 都出现了，所以最小的缺失正整数是 3

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 出现了，但 2 没有出现，所以最小的缺失正整数是 2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正整数 1 没有出现，所以答案是 1

提示

• 1 <= nums.length <= 5 * 10^5
• -2^31 <= nums[i] <= 2^31 - 1

解题思路

原地哈希法

这道题的关键是要在 O(n) 时间复杂度和 O(1) 空间复杂度内解决。我们可以利用数组本身作为哈希表，将数字放到对应的位置上。

关键点：

• 数组长度为 n，那么缺失的第一个正整数一定在 [1, n+1] 范围内
• 可以将数字 k 放到数组的第 k-1 个位置上
• 遍历完成后，第一个不在对应位置上的数字的下标加 1 就是答案

具体步骤：

1. 遍历数组，对于数字 k，如果 k 在 [1,n] 范围内，就把它放到第 k-1 个位置上
2. 再次遍历数组，找到第一个不在对应位置上的数字
3. 如果都在对应位置，则返回 n+1

图解思路

算法步骤分析表

步骤 操作 状态 说明 初始状态 - [3,4,-1,1] 原始数组 第一步 交换 3 到正确位置 [1,-1,3,4] 3 放到索引 2 第二步 交换 1 到正确位置 [-1,1,3,4] 1 放到索引 0 第三步 检查数组 [-1,1,3,4] 发现索引 0 处应该是 1

状态/情况分析表

情况 输入 输出 说明 基本情况 [1,2,0] 3 1和2都在，缺3 特殊情况 [7,8,9,11,12] 1 所有数都大于n 负数情况 [-1,-2,0] 1 包含负数和0

代码实现

C# 实现

public class Solution { public int FirstMissingPositive(int[] nums) { int n = nums.Length; // 第一次遍历：将数字放到正确的位置 for (int i = 0; i < n; i++) { // 当前数字在[1,n]范围内，且不在正确位置上时进行交换 while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { int temp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = temp; } } // 第二次遍历：找到第一个不在正确位置上的数字 for (int i = 0; i < n; i++) { if (nums[i] != i + 1) { return i + 1; } } // 如果都在正确位置，返回n+1 return n + 1; }}

执行结果

• 执行用时：132 ms
• 内存消耗：52.1 MB

代码亮点

1. 🎯 利用数组本身作为哈希表，实现O(1)空间复杂度
2. 💡 通过交换操作将数字放到正确位置，避免使用额外空间
3. 🔍 细节处理：处理数组越界和重复数字的情况
4. 🎨 代码结构清晰，分为放置数字和查找缺失数字两个阶段

常见错误分析

1. 🚫 忽略数组长度为1的特殊情况
2. 🚫 没有正确处理重复数字的情况
3. 🚫 忘记处理负数和零的情况
4. 🚫 交换过程中出现死循环

解法对比

解法 时间复杂度 空间复杂度 优点 缺点 排序法 O(nlogn) O(1) 实现简单 时间复杂度高 哈希表法 O(n) O(n) 思路直观 空间复杂度高 原地哈希法 O(n) O(1) 符合题目要求 实现较复杂

相关题目

• 缺失数字 - 简单
• 找到所有数组中消失的数字 - 简单
• 数组中重复的数据 - 中等