LeetCode 41. 缺失的第一个正数
题目描述
题意分析
给定一个未排序整数数组，找出其中没有出现的最小正整数。正整数从
1开始，数组可能包含负数、零和重复值；题目要求 $O(n)$ 时间和 $O(1)$ 额外空间，因此不能依靠排序或额外的集合记录所有值。长度为
n的数组最多容纳n个不同的正整数。如果1到n全部出现，答案就是n + 1；否则答案一定是1到n中缺少的某个数。因此只需记录[1, n]的出现情况，其他数值可以忽略。数组本身正好有
n个位置，可以用下标x - 1表示正整数x是否出现。通过交换把值放回对应位置，既能保留所有原始数值，又不需要额外开辟标记空间；这种做法会改变输入数组的顺序。
解法：原地交换归位
核心思路
[!blue]
规定值
x的正确位置是下标x - 1，只对1 <= x <= n的值执行归位。遍历到下标i时，如果当前值有效，并且目标位置还没有相同的值，就交换这两个位置，让当前值回到自己的位置。交换之后，
i处会收到原来目标位置上的另一个值。这个新值也可能需要归位，不能直接跳到下一个下标；因此对同一位置反复检查，直到当前值无效、已经归位，或其目标位置已经保存了相同值。目标位置已经有相同值时必须停止。此时这个正整数的出现信息已经被记录，当前位置上的重复值没有必要再移动；继续交换只会让两个相同值来回互换，数组没有变化，循环也无法结束。
每次真正执行交换，都会让目标位置从错误变为正确。已经归位的值不会再被有效交换移走：只有同样的值会以这个位置为目标，而重复值判断会阻止这次交换。因此整个过程中正确位置只会增加，总交换次数最多为
n，内外两层循环并不意味着平方时间。归位结束后，凡是出现过的有效值
x，其对应位置一定保存着x；交换不会删除数值，所有需要继续归位的换入值也都被检查过。再从左向右找第一个nums[i] != i + 1的位置，就说明i + 1没有出现，而更小的正整数都已经归位，它正是答案。若所有位置都匹配，则返回n + 1。
解题步骤
- 记录数组长度
n，从左到右遍历每个下标i。- 先检查当前值是否在
[1, n]，只有有效时才读取目标位置nums[i] - 1，避免越界。- 若目标位置还没有相同值，先保存目标下标，再交换两个位置，并继续检查换入
i的新值。- 当当前位置不再需要交换时，继续处理下一个下标。
- 归位完成后重新扫描，返回第一个不匹配位置对应的
i + 1；全部匹配则返回n + 1。
代码实现
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
// 先检查有效值域，再判断目标位置；重复值到位就停止交换。
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
// 本次至少归位一个值，换回当前位置的新值继续检查。
int target = nums[i] - 1;
int temp = nums[target];
nums[target] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
func firstMissingPositive(nums []int) int {
n := len(nums)
for i := 0; i < n; i++ {
// 先检查有效值域，再判断目标位置；重复值到位就停止交换。
for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
// 本次至少归位一个值，换回当前位置的新值继续检查。
target := nums[i] - 1
nums[target], nums[i] = nums[i], nums[target]
}
}
for i := 0; i < n; i++ {
if nums[i] != i+1 {
return i + 1
}
}
return n + 1
}
复杂度分析
- 时间复杂度：$O(n)$，每次交换至少让一个值归位，总交换次数不超过
n。- 空间复杂度：$O(1)$，直接修改输入数组。
关键点总结
[!green]
- 只需归位
[1, n]内的值，其他值不可能影响答案。- 交换要使用
while，继续处理被换到当前位置的新值。- 目标位置已有相同值时必须停止，避免重复值导致死循环。
易错点总结
[!yellow]
- 交换前必须检查值的范围，否则目标下标可能越界。
- 缺少重复值判断时，两个相同元素会无限交换。
- 只交换一次会漏掉被换回来的、仍需归位的值。
- 最终返回的是
i + 1；全部匹配时返回n + 1。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 448. 找到所有数组中消失的数字 | 简单 | 同样把值映射到原数组下标作标记，本题还需先忽略范围外整数并寻找最小正数。 |