缺失的第一个正数-526互联

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数

1. 暴力排序查找

排序+去重+二分查找

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        unique(nums.begin(),nums.end());
        auto i = upper_bound(nums.begin(),nums.end(),0);//找第一个比0大的位置
        int num = 1;
        while(i!=nums.end()){
            if(*i!=num) return num;
            num++;
            i++;
        }
        return num;
    }
};

2. 哈希表

哈希表存储

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
       unordered_set<int> s;
       for(int i=0;i<nums.size();i++)
            s.insert(nums[i]);
        int num = 1;
        while(1){
            if(s.find(num)==s.end()) return num;
            num++;
        }
        return num;
    }
};

3. 常数空间和线性时间

在数组范围内的数放到对应位置，然后再次遍历

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
       for(int i=0;i<n;i++)
            while(nums[i]>0&&nums[i]<n&&nums[i]!=nums[nums[i]-1]) 
                swap(nums[i],nums[nums[i]-1]);
        int i = 0;
        while(i<n){
            if(nums[i]!=i+1) return i+1;
            i++;
        }
        return i+1;
    }
};