41

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int tmp=INT_MAX, n=nums.size();
        for(int num: nums)
            if(num>0){ tmp = num; break;}
        for(int &num: nums)
            if(num <= 0) num = tmp;
        for(int num: nums){
            num = abs(num);
            if(num == n) nums[0] = -abs(nums[0]);
            if(num>0 && num<n)
                nums[num] = -abs(nums[num]);
        }
        for(int i=1; i<n; i++)
            if(nums[i] > 0) return i;
        if(nums[0] > 0)
            return n;
        return n+1;
    }
};