Given an unsorted integer array, find the first missing positive integer.
For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
The original problem is here.
The original code is here.
I solve this problem in C++, as below:
/*
*First Missing Positive
*Author: shuaijiang
*Email: [email protected]
*/
#include<iostream>
#include<vector>
#include<map>
#include<stdlib.h>
using namespace std;
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int size = nums.size();
bool positive = false;
sort(nums.begin(),nums.end());
for(int i=0;i<size;i++){
if(positive){
if(nums[i]-nums[i-1] > 1)
return nums[i-1] + 1;
}
else{
if(nums[i]>0)
positive = true;
if(nums[i]>1)
return 1;
}
}
if(positive)
return nums[size-1]+1;
return 1;
}
};
In the solution, first sort the vector. Then, tranversal the vector and find the positive part, and take the first missing positive.