class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n;  i ++) 
            while (nums[i] >= 1 && 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;
    }
};

哈希表 （Time:$O(N)$, Space: $O(N)$）

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int, int> hash;
        for (auto x : nums) hash[x] ++; //把所有数插入哈希表

        int res = 1;
        while (hash.count(res)) res ++; //从小到大枚举每一个正整数，直到找到第一个没有在哈希表中出现过的正整数位置
        return res; 
    }
};