classSolution{public:intfirstMissingPositive(vector<int>&nums){// We are creating a set to store only the positive numbers,// This will help us to find first missing positiveunordered_set<int>seen;// Step 1: Add only the positive numbers in the setfor(intnum:nums){// If it is positive, then insert itif(num>0){seen.insert(num);// Store it}}// Step 2: Check for the first missing positiveinti=1;// Start checking from 1, 2, 3, ... until we not found one which is not presentwhile(true){// If `i` is not present in the `set`if(seen.find(i)==seen.end()){returni;// return it}i++;// Move to the next number to check}}};
classSolution{public:intfirstMissingPositive(vector<int>&nums){intn=nums.size();// Step 1: Replace irrelevant numbers (zeros, negatives, > n)for(inti=0;i<n;i++){// If the nums[i] is a zero, negative, or > n// Not in our range: [1, n]if(nums[i]<=0||nums[i]>n){nums[i]=n+1;// Replace it with `n + 1`}}// Step 2: Mark the numbers which are presentfor(inti=0;i<n;i++){intnum=abs(nums[i]);// Why abs(), if the number is already negative marked previouslyintindex=num-1;// Corresponding index of `num`// Only take those numbers which is in our range: [1, n]if(num<=n){// mark the number at `index` negative, to indicate it is present nums[index]=-abs(nums[index]);}}// Step 3: Find the first postive numberfor(inti=0;i<n;i++){// If the nums[i] is positive, it is missingif(nums[i]>0){returni+1;// return the missing number}}// if all the numbers between the range: [1, n] are present// Return the number after nreturnn+1;}};
Warning
LINK
You are about to visit a link which has been flagged with the above content warnings. Do you wish to continue?