## [41\. First Missing Positive](https://leetcode.com/problems/first-missing-positive/)

Given an unsorted integer array `nums`. Return the _smallest positive integer_ that is _not present_ in `nums`.

You must implement an algorithm that runs in `O(n)` time and uses `O(1)` auxiliary space.

**Example 1:**

**Input:** nums = \[1,2,0\]
**Output:** 3
**Explanation:** The numbers in the range \[1,2\] are all in the array.

**Example 2:**

**Input:** nums = \[3,4,-1,1\]
**Output:** 2
**Explanation:** 1 is in the array but 2 is missing.

**Example 3:**

**Input:** nums = \[7,8,9,11,12\]
**Output:** 1
**Explanation:** The smallest positive integer 1 is missing.

**Constraints:**

- `1 <= nums.length <= 105`
- `-231 <= nums[i] <= 231 - 1`

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            // 若數字大於 0 且小於等於 n，且該位置上的數字不等於當前數字，則進行交換
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1)
                return i + 1;
        }
        return n + 1;
    }
};

:::success
- 時間複雜度：$O(N)$
- 空間複雜度：$O(1)$
:::