41. 缺失的第一个正数

#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
    Solution(){}
    ~Solution(){}
    int firstMissingPositive(vector<int>& nums) {
        //最小的正整数一定在1-N之间，或者是N+1
        int len=nums.size();
        //将非正数变成N+1
        for (int i = 0; i < len; i++)
        {
            if (nums[i]<=0)
            {
                nums[i]=len+1;
            }
        }
        //当前数的绝对值减一，并将处于该结果位置的数取负
        for (int i = 0; i < len; i++)
        {
            int temp=abs(nums[i]);
            if (temp<len+1)
            {
                nums[temp-1]=-abs(nums[temp-1]);
            }
        }
        //第一个正数出现的位置即为最小正整数
        for (int i=0; i < len; i++)
        {
            if (nums[i]>0)
            {
                return i+1; 
            }
            
        }
        //如果全为负数，则是N+1
        return len+1;
        
    }
};
int main(){
    Solution s;
    vector<int> nums={3,4,-1,1};
    cout<<s.firstMissingPositive(nums);
    return 0;
}