class Solution {
public:
int firstMissingPositive(int arr[], int n) {
int i, temp;
for (i = 0; i < n; i++)
{
while(arr[i] != i+1 && arr[i] > 0 && arr[i] <= n && arr[i] != arr[arr[i]1])
{
temp = arr[arr[i]1];
arr[arr[i]1] = arr[i];
arr[i] = temp;
}
}
for(i = 0; i < n; i++)
{
if (arr[i] != i+1)
return i+1;
}
return i+1;
}
};
Sharing my 8ms c++ accepted solution


Nice implementation! My Python version based on your idea. Thanks for sharing!
class Solution: # @param A, a list of integers # @return an integer def firstMissingPositive(self, A): #works when A contains duplicates for i in range(len(A)): num = A[i] while num <= len(A) and num > 0: if num != A[num1]: temp = A[num1] A[num1] = num num = temp else: break for i in range(len(A)): if A[i] != i+1: return i+1 return len(A)+1