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.
ATTENTION：
we need to find the relationship between subscripts and array value.
Correct order is the subscripts i corresponding i+1,which means arr[i]=i+1;
So if you find this value is not the correct corresponding just swap it to the right place.
if(arr[i]!=i+1&&arr[i]>=1&&arr[i]<=n&&arr[arr[i]-1]!=arr[i])
This code is the most important one,but you need to pay attention that if arr[i]-1<0
the arr will outrange so when we dealing with arrays we need to pay attention to its
subscripts
#include<iostream> #include<string> #include<stdio.h> #include<string.h> #include<iomanip> #include<vector> #include<list> #include<queue> #include<algorithm> #include<stack> #include<map> using namespace std; //solve function class Solution { public: int firstMissingPositive(vector<int>& arr) { int res,n=arr.size(); for(int i=0;i<n;) { if(arr[i]!=i+1&&arr[i]>=1&&arr[i]<=n&&arr[arr[i]-1]!=arr[i]) { swap(arr[i],arr[arr[i]-1]); } else { i++; } } for(int i=0;i<n;i++) { if(arr[i]!=i+1) { res=i+1; return res; } } res=n+1; return res; } }; int main() { Solution s; vector<int> arr={0,0,2}; int res; res=s.firstMissingPositive(arr); cout<<res<<endl; return 0; }
LeetCode开心刷题二十二天——41. First Missing Positive
原文：https://www.cnblogs.com/Marigolci/p/11216840.html