41. 缺失的第一个正数
3 min
题目
解法：递归归位
思路
核心思想是利用数组下标作为哈希表，将每个正数x放置到索引x-1的位置。正确性在于：最小缺失正整数必在[1, n+1]区间，通过归位操作后，第一个位置i上不满足nums[i]=i+1的i+1即为答案。若全部归位则返回n+1。
- Step 1: 遍历数组，对每个元素递归调用place函数
- Step 2: place函数检查数值x是否在[1, n]范围内且未归位
- Step 3: 若需归位，交换x到索引x-1处，并递归处理被替换的元素
- Step 4: 再次遍历数组，找到第一个nums[i]≠i+1的位置返回i+1
- Step 5: 若全部匹配则返回n+1
复杂度
- 时间复杂度: 。每个元素最多被归位一次，递归总深度不超过n。
- 空间复杂度: 。递归调用栈深度在最坏情况下（如完全逆序数组）可达n层。
代码
class Solution {
public:
// 递归函数：尝试将数值 x 放置到正确的位置 (index = x - 1)
void place(int x, vector<int>& nums) {
// 判断 x 是否为有效正数且在数组范围内
if (x >= 1 && x <= nums.size()) {
int targetIdx = x - 1;
// 如果目标位置还不是 x，则进行操作
if (nums[targetIdx] != x) {
int nextVal = nums[targetIdx]; // 取出当前占据该位置的数
nums[targetIdx] = x; // 把 x 放进去
place(nextVal, nums); // 递归处理刚才取出来的那个数
}
}
}
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
place(nums[i], nums);
}
}
class Solution {
public:
// 递归函数：尝试将数值 x 放置到正确的位置 (index = x - 1)
void place(int x, vector<int>& nums) {
// 判断 x 是否为有效正数且在数组范围内
if (x >= 1 && x <= nums.size()) {
int targetIdx = x - 1;
// 如果目标位置还不是 x，则进行操作
if (nums[targetIdx] != x) {
int nextVal = nums[targetIdx]; // 取出当前占据该位置的数
nums[targetIdx] = x; // 把 x 放进去
place(nextVal, nums); // 递归处理刚才取出来的那个数
}
}
}
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
place(nums[i], nums);
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
};