答案是将1~n的数放到对应索引0~n-1位置，遍历交换后首次出现nums[i]≠i+1时返回i+1，否则返回n+1。
要找出数组中最小的缺失正整数（即未出现的最小正整数 1, 2, 3, …），关键在于不依赖排序或额外空间，用原地哈希思想在 O(n) 时间、O(1) 空间内解决。
核心思路：把数字放到对应下标位置
正整数 1 应该放在索引 0，2 放在索引 1，…，k 放在索引 k−1。遍历数组，对每个合法数字（1 ≤ num ≤ n）尝试将其交换到正确位置，跳过重复、越界或已在正确位置的元素。
具体步骤
- 设数组长度为 n，只关心值在 [1, n] 范围内的数（超出的数不可能是答案，也不影响前 n 个位置的判断）
- 用 while 循环对每个位置 i 做校验：
– 若 $nums[$i] == $i + 1，已就位，跳过
– 若 $nums[$i] 是 [1, n] 内的数，且它当前所在位置不是它的目标位置（即 $nums[$i] != $nums[$nums[$i] - 1]），则交换
– 否则（重复值或越界），跳过 - 再次遍历数组，第一个满足 $nums[$i] != $i + 1 的位置 i，答案就是 $i + 1
- 若全部匹配（即 1 到 n 都存在），答案是 n + 1
PHP 实现示例
<?php
function firstMissingPositive($nums) {
$n = count($nums);
// 第一遍：原地放置
for ($i = 0; $i
while ($nums[$i] >= 1 && $nums[$i]
$nums[$i] != $nums[$nums[$i] - 1]) {
$j = $nums[$i] - 1;
[$nums[$i], $nums[$j]] = [$nums[$j], $nums[$i]]; // PHP 7.1+ 解构赋值
}
}
// 第二遍：找第一个错位
for ($i = 0; $i
if ($nums[$i] != $i + 1) {
return $i + 1;
}
}
return $n + 1;
}
// 测试
var_dump(firstMissingPositive([1, 2, 0])); // 3
var_dump(firstMissingPositive([3, 4, -1, 1])); // 2
var_dump(firstMissingPositive([7, 8, 9, 11, 12])); // 1
?>
注意事项
- 交换时务必先检查 $nums[$i] != $nums[$nums[$i] - 1]，避免死循环（比如 [1,1] 中反复交换）
- 使用解构赋值交换需 PHP ≥ 7.1；低版本可用临时变量
- 负数和大于 n 的数无需处理，它们不影响 1~n 的存在性判断
