普通数组-----缺失的第一个正数
🔥个人主页：Milestone-里程碑
❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>
<<Git>><<MySQL>>
🌟心向往之行必能至
题目描述
给你一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数。
进阶：你能实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案吗？
示例 1：输入：nums = [1,2,0]输出：3
示例 2：输入：nums = [3,4,-1,1]输出：2
示例 3：输入：nums = [7,8,9,11,12]输出：1
数据范围：
1 <= nums.length <= 5 * 10^5-2^31 <= nums[i] <= 2^31 - 1
解题思路
这道题是 LeetCode Hot100 中的困难级高频题，核心难点在于O (n) 时间复杂度 + O (1) 空间复杂度的限制，常规的哈希表 / 排序方法都无法满足要求，因此我们采用原地哈希的思路：
核心思想
利用数组本身作为哈希表，将数值为k的正整数放到下标为k-1的位置：
- 数字
1→ 下标0 - 数字
2→ 下标1 - ...
- 数字
n→ 下标n-1（n为数组长度）
解题步骤
- 原地归位：遍历数组，将每个有效范围内的正整数交换到正确的位置；
- 查找缺失值：再次遍历数组，第一个下标
i对应的值不等于i+1的位置，i+1就是缺失的最小正整数； - 边界处理：如果数组中
1~n都完整存在，返回n+1。
代码实现（C++）
cpp
运行
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); // 第一步：将每个正整数交换到正确的位置 for (int i = 0; i < n; ++i) { // 循环交换：当前数是有效正整数，且不在正确位置时，持续交换 while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) { // 计算当前数应该存放的下标 int j = nums[i] - 1; // 交换元素，将nums[i]放到正确位置 swap(nums[i], nums[j]); } } // 第二步：遍历查找第一个缺失的正整数 for (int i = 0; i < n; ++i) { if (nums[i] != i + 1) { return i + 1; } } // 第三步：1~n都存在，返回n+1 return n + 1; } };代码逐行解析
1. 变量定义
cpp
运行
int n = nums.size();定义数组长度n，简化后续代码，同时明确有效正整数的范围是[1, n]（超过n的正整数不可能是答案）。
2. 原地归位循环
cpp
运行
for (int i = 0; i < n; ++i) { while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) { int j = nums[i] - 1; swap(nums[i], nums[j]); } }- 外层
for循环：遍历数组每一个位置，确保每个数都被归位； - 内层
while循环：持续交换直到当前数归位 / 超出范围，三个条件缺一不可：1 <= nums[i] <= n：只处理有效范围内的正整数（负数、0、大于 n 的数直接忽略）；nums[i] != nums[nums[i]-1]：避免重复元素死循环（比如两个 1 交换会无限循环）；
swap(nums[i], nums[j])：将当前数交换到它应该在的位置。
3. 查找缺失值
cpp
运行
for (int i = 0; i < n; ++i) { if (nums[i] != i + 1) { return i + 1; } } return n + 1;遍历归位后的数组：
- 若
nums[i] != i+1，说明i+1是缺失的最小正整数； - 若所有位置都正确，说明
1~n都存在，返回n+1。
复杂度分析
- 时间复杂度：
O(n)每个元素最多被交换1 次就能归位，两层循环总操作次数是线性的。 - 空间复杂度：
O(1)仅使用了常数个临时变量，没有开辟额外的数组 / 哈希表，完全满足题目进阶要求。
测试用例验证
- 用例
[1,2,0]：归位后[1,2,0]，遍历发现下标 2 值≠3，返回 3； - 用例
[3,4,-1,1]：归位后[1,-1,3,4]，遍历发现下标 1 值≠2，返回 2； - 用例
[7,8,9,11,12]：归位后无变化，遍历发现下标 0 值≠1，返回 1。
总结
这道题的核心是原地哈希思想，通过利用数组自身存储映射关系，突破了常数空间的限制，是 LeetCode 高频考察的思维题。
掌握这个思路后，同类的「原地修改数组找缺失值」题目都可以用相同逻辑解决～