手撕Hard--缺失的第一个正数

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int,int> hash;
        for(int i=0;i<nums.size();i++){
            if(nums[i]>0)hash[nums[i]]++;
        }
        int res=0;
        while(hash[++res]);
        return res;
    }
};

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;
    }
};
 

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size(); // 获取数组的长度
        // 第一次遍历数组，将每个正整数 nums[i] 放置到索引为 nums[i] - 1 的位置上
        // 即将 1 放到索引 0，将 2 放到索引 1，以此类推，直到 n 放到索引 n - 1
        for (int i = 0; i < n; ++i) {
            // 只处理大于 0 且小于等于 n 的元素，并且确保 nums[i] 不在正确位置上
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]); // 将 nums[i] 放到正确的位置上
            }
        }
        // 第二次遍历数组，找到第一个不在正确位置上的数，即缺失的最小正整数
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) { // 如果 nums[i] 不等于 i + 1，表示缺失 i + 1
                return i + 1;
            }
        }
        // 如果数组中包含 1 到 n 的所有正整数，则缺失的是 n + 1
        return n + 1;
    }
};

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size(), ans = n + 1; // 获取数组长度，并初始化结果为 n+1
        auto judge = [&](int x){return x >= 1 && x <= n;}; // 定义 lambda 表达式，用于判断数字是否在有效范围内
        for(int& m : nums){ // 将不在有效范围内的数字置为 0
            if(!judge(m)) m = 0;
        }
        for(int i = 0; i < n; i ++){ // 将出现过的正整数标记在数组中，负数表示已经出现过
            if(nums[i] > 0){
                int t = nums[i];
                nums[i] = 0;
                while(t > 0){ // 不断迭代，直到 t <= 0
                    int x = nums[t - 1];
                    nums[t - 1] = -1; // 将出现过的正整数标记为 -1
                    t = x;
                }  
            }
        }
        for(int i = 0; i < n; i ++){ // 寻找第一个未被标记的数，其索引 + 1 即为结果
            if(nums[i] != -1){
                ans = i + 1;
                break;
            }
        }
        return ans; // 返回结果
    }
};