leetcode41. 缺失的第一个正数

思路

nums中有n个数，若nums中依次为1-n，则缺失的数为n+1，若其中有重复或者负数，那么这个缺失的数必在1-n中。则可以用nums这个数组作为哈希地址，由于存在重复数字，我们可以每次取nums[i]的绝对值，然后将其对应的nums的角标位置变成负数，最后遍历nums，找到第一个正数，其下标则为缺失值。

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 k=abs(nums[i]);
           if(k<=n)nums[k-1]=-abs(nums[k-1]);
        }
        for(int i=0;i<n;i++){
           if(nums[i]>0)return i+1;
        }
        return n+1;
    }
};