41. First Missing Positive

 

41. First Missing Positive

Hard

2244664FavoriteShare

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0] Output: 3

Example 2:

Input: [3,4,-1,1] Output: 2

Example 3:

Input: [7,8,9,11,12] Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

Accepted

255,211

Submissions

848,595

class Solution { public: int firstMissingPositive(vector<int>& nums) { map<int,int> mp; for(int i=0;i<nums.size();i++){ mp[nums[i]]=1; } map<int,int>::iterator it=mp.end();//map会根据键的大小自动排序 int n=it->first; //cout<<n<<endl; for(int i=1;i<=n;i++){ if(mp[i]!=1) return i; } return n+1; } };