🔥个人主页：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 为数组长度）

解题步骤

1. 原地归位：遍历数组，将每个有效范围内的正整数交换到正确的位置；
2. 查找缺失值：再次遍历数组，第一个下标 i 对应的值不等于 i+1 的位置，i+1 就是缺失的最小正整数；
3. 边界处理：如果数组中 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. 1 <= nums[i] <= n：只处理有效范围内的正整数（负数、0、大于 n 的数直接忽略）；
  2. 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. 用例 [1,2,0]：归位后 [1,2,0]，遍历发现下标 2 值≠3，返回 3；
2. 用例 [3,4,-1,1]：归位后 [1,-1,3,4]，遍历发现下标 1 值≠2，返回 2；
3. 用例 [7,8,9,11,12]：归位后无变化，遍历发现下标 0 值≠1，返回 1。

---

总结

这道题的核心是原地哈希思想，通过利用数组自身存储映射关系，突破了常数空间的限制，是 LeetCode 高频考察的思维题。

掌握这个思路后，同类的「原地修改数组找缺失值」题目都可以用相同逻辑解决～