# 41.缺失的第一个正数 (Hard)

## 问题描述
[41. 缺失的第一个正数 (Hard)](https://leetcode.cn/problems/first-missing-positive/)

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

请你实现时间复杂度为 `O(n)` 并且只使用常数级别额外空间的解决方案。

**示例 1：**

```
输入：nums = [1,2,0]
输出：3

```

**示例 2：**

```
输入：nums = [3,4,-1,1]
输出：2

```

**示例 3：**

```
输入：nums = [7,8,9,11,12]
输出：1

```

**提示：**

- `1 <= nums.length <= 5 * 10⁵`
- `-2³¹ <= nums[i] <= 2³¹ - 1`

## 解题思路
### 标记
在`nums[i]`数组上做标记，我们可以将`nums`数组中的负数都设为`n + 1`，令`num = abs(nums[i])`，然后将`nums[num - 1]`取反，最后遍历修改后的`nums[i]`，如果都是负数，返回`n + 1`，否则返回碰到的第一个非负数的索引加一；

### 置换
如果`nums[i] <= nums.size() && nums[i] > 0`，那么就将它与`nums[num[i] - 1]`置换，为了防止死循环，还要判断`nums[i] != nums[nums[i] - 1]`

## 代码
### 标记
```cpp
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int& num: nums) {
            if (num <= 0) {
                num = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
};
// @lc code=end
```

### 置换
```cpp
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            while (nums[i] > 0 && nums[i] <= nums.size() && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                std::swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.size() + 1;
    }
};
```