🔗 缺失的第一个正数

题目来源：41. 缺失的第一个正数 – 力扣（LeetCode）

---

📌 题目描述

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

• 要求：
  • 时间复杂度为 O(n)。
  • 只使用常数级别额外空间（即不能使用哈希表等额外数据结构）。

---

✅ 示例解析

示例 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 <= nums.length <= 10⁵
• -2³¹ <= nums[i] <= 2³¹ - 1

---

💡 解法：原地哈希（利用数组索引）—— O(n) 时间，O(1) 空间

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0) {
                nums[i] = len + 1;
            }
        }

        for (int i = 0; i < len; i++) {
            int p = Math.abs(nums[i]);
            if (p <= len) {
                nums[p - 1] = -Math.abs(nums[p - 1]);
            }
        }
        
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
 
        return len + 1;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  • 三次遍历数组，每次 O(n)，总体为线性时间。
• 空间复杂度：O(1)
  • 仅使用常数个额外变量（如 i, p）
  • 所有操作均在原数组 nums 上进行，未使用额外数组或哈希表。

---

🧩 解题思路

1. 核心思想：原地哈希（Index as Hash Key）
   • 数组长度为 n，则最小缺失正数一定在 [1, n+1] 范围内。
   • 利用数组索引 i 来表示数字 i+1 是否存在。
   • 通过负号标记某个位置是否被“占用”。
2. 三步走策略： 步骤 1：预处理，清除干扰项
   • 将所有 <= 0 的数替换为 n + 1（一个超出范围的数）
   • 目的：确保数组中所有数都是正数，便于后续用负号标记。
   步骤 2：标记存在的数
   • 遍历每个元素 nums[i]，取其绝对值 p = |nums[i]|
   • 若 p <= n，说明 p 是一个有效的正数（在 1~n 范围内）
   • 将 nums[p - 1] 设为负数（-|nums[p-1]|），表示数字 p 存在
   • 使用 Math.abs 是为了避免重复访问时因负数导致错误。
   步骤 3：查找第一个未标记的位置
   • 再次遍历数组，找到第一个 nums[i] > 0 的位置
   • 说明数字 i + 1 不存在，返回 i + 1
   • 若所有位置都 <= 0，说明 1~n 都存在，返回 n + 1
3. 举例说明：
   对 nums = [3,4,-1,1]：
   • Step 1 后：[3,4,5,1]（-1 → 5）
   • Step 2 过程：
     • i=0: p=3 ≤ 4 → nums[2] = -5 → [3,4,-5,1]
     • i=1: p=4 ≤ 4 → nums[3] = -1 → [3,4,-5,-1]
     • i=2: p=5 > 4 → 忽略
     • i=3: p=1 ≤ 4 → nums[0] = -3 → [-3,4,-5,-1]
   • Step 3：nums[1] = 4 > 0 → 返回 1 + 1 = 2 ✅
4. 边界处理：
   • 所有数都为正且连续（如 [1,2,3]）→ 返回 4
   • 所有数都大于 n（如 [7,8,9]）→ 返回 1