题解 | #缺失的第一个正整数#

参考：https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int minNumberDisappeared(vector<int>& nums) {
        // write code here
        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;
    }
};

/*
// 使用哈希表
lass Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
        // write code here
        unordered_map<int, int> tb;
        int min_val = INT_MAX;
        int max_val = -1;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] > 0){
                min_val = min(min_val, nums[i]);
                max_val = max(max_val, nums[i]);
                tb[nums[i]] += 1;
            }
        }
        
        if(min_val > 1){
            return 1;
        }
        int res = min_val+1;
        while(res <= max_val){
            if(tb.find(res) == tb.end()){
                break;
            }
            res++;
        }
        return res;
    }
};

*/