本题采用原地哈希（桶排序/基数排序思想）算法解决“缺失的第一个正数”问题。其核心本质是利用数组的索引下标作为天然的哈希表键值，通过不断的置换操作将符合范围的正整数强制归位到对应的物理位置。当前源码实现了在不占用额外内存空间的前提下进行数据的就位，最终走向是通过第二次线性扫描首个未就位的元素索引来精确锁定目标缺失值。

一、 问题本质与数据模型

对于长度为 n 的整数数组 nums，我们需要寻找没有出现的最小正整数。在处理该问题时，首先需要通过数学归纳确立结果的物理边界：

• 最理想情况：如果数组包含从 1 到 n 的所有正整数 [1, 2, 3, ..., n]，那么缺失的第一个正整数必然为 n + 1。

• 非理想情况：如果数组中存在小于等于 0 的数、大于 n 的数、或是重复的数，根据抽屉原理（鸽巢原理），缺失的第一个正整数必然落在 [1, n] 的有效闭区间内。

由此可得，最终的答案必然位于 [1, n + 1] 之间。

这一数学边界直接决定了我们的数据模型：我们完全不需要理会小于等于 0 或大于 n 的数字，只需要聚焦于满足 1 <= nums[i] <= n 范围内的正整数，并设法验证它们是否全部就位。

在不被允许开辟额外哈希表的前提下，算法将原数组自身视为一个哈希表。对于任意满足范围的数值 x，它在哈希表中的标准归宿就是数组的 x - 1 下标位置。即算法最终的目标是让数组尽可能满足：

nums[i] == i + 1

二、 算法演进对比

在解决动态正整数连续性判定问题时，原地哈希置换法在时空资源的利用效率上达成了最优解：

解法名称	时间复杂度	空间复杂度	核心原理	物理缺陷 / 瓶颈
标准双重循环排序	O(n log n)	O(1) 或 O(n)	先对全数组进行快速排序或归并排序，随后线性扫描查找断层	时间开销受限于排序上限，无法达到线性时间要求
辅助哈希集合去重	O(n)	O(n)	将所有数字存入 HashSet，随后从 1 开始依次在集合中查询是否存在	引入了与原数据等长的额外内存空间开销，违反常数空间约束
原地哈希置换（当前解法）	O(n)	O(1)	利用数组下标作为哈希地址，通过不断交换元素让正确的数据归位	需要在原数组内部进行直接的数据改写与位置置换

三、 原地哈希置换的核心控制逻辑

当前源码的卓越性在于通过一个内嵌的 while 循环实现了无额外空间的“数据自动归位”。其核心判定条件由三部分组成：

while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])

1. 数值合法性过滤：nums[i] >= 1 && nums[i] <= n

只有当前元素位于 [1, n] 区间内时，它才拥有在数组中被归位的资格。任何负数、0 以及超出数组长度的大整数都无法匹配任何合法的数组下标，直接跳过。

2. 目标冲突判定：nums[nums[i] - 1] != nums[i]

这是防止算法陷入死循环的核心防护网。

• 设当前位置的数值为 x = nums[i]，它本应该待的地方是目标索引 j = x - 1。

• 只有当目标位置上的数值 nums[j] 还不等于 x 时（即 nums[nums[i] - 1] != nums[i]），才需要执行交换。

• 逻辑证明：如果满足 nums[j] == x，说明该数字在目标位置上已经存在（遇到了重复元素）。此时如果继续交换，当前位置的值不会发生改变，while 循环将永远无法退出。

3. 为什么必须使用 while 而不是 if？

当我们将 nums[i] 交换到它应该去的目的地 nums[j] 后，原本待在 nums[j] 的那个未知元素被换到了当前位置 i。这个换过来的新元素同样可能是个合法的、需要归位的数字。因此必须使用 while 循环不断对当前位置 i 上的新元素进行重复判定与置换，直到换过来的元素是一个非法值或是一个已经正确就位的元素为止。

四、 算法执行状态机步进示例

以输入数据 nums = [3, 4, -1, 1] 为例（此时数组长度 n = 4），外层循环变量 i 推进时的内部置换状态演进过程如下表所示：

步骤	外层索引 i	当前元素 nums[i]	满足 while 条件与置换过程	数组内部实时元素状态	物理意义说明
初始	-	-	-	[3, 4, -1, 1]	原始无序状态
1	0	3	满足。目标索引 j = 3-1 = 2。   与 nums[2](-1) 互换。	[-1, 4, 3, 1]	数字 3 成功归位到下标 2
2	0	-1	-1 < 1，不满足条件，跳出 while。	[-1, 4, 3, 1]	当前位置为无效值，指针右移
3	1	4	满足。目标索引 j = 4-1 = 3。   与 nums[3](1) 互换。	[-1, 1, 3, 4]	数字 4 成功归位到下标 3
4	1	1	满足。目标索引 j = 1-1 = 0。   与 nums[0](-1) 互换。	[1, -1, 3, 4]	数字 1 成功归位到下标 0
5	1	-1	-1 < 1，不满足条件，跳出 while。	[1, -1, 3, 4]	当前位置为无效值，指针右移
6	2	3	nums[2] == 2+1，已正确就位，跳过。	[1, -1, 3, 4]	指针右移
7	3	4	nums[3] == 3+1，已正确就位，跳过。	[1, -1, 3, 4]	第一轮置换完全结束
扫描	从 0 到 3	-	检查到 nums[1] = -1 != 2	触发 return i + 1	输出结果：2

五、源码实现

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 边界安全检查
        if (nums == null || nums.length == 0) {
            return 1;
        }
        
        int n = nums.length;
        
        // 步骤 1：原地哈希置换，尝试将每个满足 [1, n] 范围的数字 x 放到对应的下标 x - 1 上
        for (int i = 0; i < n; i++) {
            // 使用 while 循环，持续对换到当前位置 i 的新元素进行就位处理
            // 条件包含：数值在合法区间内，且目标位置上的数值与当前数值不相等（防重复死循环）
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // 计算目标归宿索引
                int j = nums[i] - 1;
                
                // 进行原地元素对调
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        
        // 步骤 2：再次扫描调整后的数组，寻找第一个没有正确就位的物理位置
        for (int i = 0; i < n; i++) {
            // 如果当前位置的值不等于 索引 + 1，说明该正整数缺失
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        // 步骤 3：如果数组中 [1, n] 的所有正整数都正确就位了，则缺失的必然是 n + 1
        return n + 1;
    }
}

六、 复杂度极限分析

1. 时间复杂度 O(n)

• 精确摊还分析：虽然代码的结构上表现为 for 循环内部嵌套了一个 while 循环，但我们不能简单地将其评估为平方阶。从物理置换的本质来看，每一次成功的 swap 操作，都必然会将至少一个原本错位的数字送入到它长久正确的最终位置（即满足 nums[j] == j + 1）。

• 结论：一旦一个元素正确就位，它就绝不会再次被挪动。由于数组中总共只有 n 个元素，整个算法生命周期里发生的总交换次数绝对不会超过 n - 1 次。因此，while 循环的平均摊还时间开销为常数阶 O(1)，结合随后的第二次线性扫描，综合总时间复杂度稳定在 O(n)。

2. 空间复杂度 O(1)

• 分析：算法所有的元素移位、调配与对调逻辑全部直接施加在传入的原始 nums 数组内存块上展开（原地算法）。执行期间，除独立声明了 n, i, j, temp 等有限个用于控制迭代和辅助对调的基础类型整型变量外，没有申请任何与输入规模相关的外部数据结构。

• 结论：额外内存的消耗固定为常数阶，空间复杂度为严格的 O(1)。