LeetCode First Missing Positive

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.

解題思路：數組總共有n個數，若都是連續的，最大的數是n，也就是說返回的值最大為n+1，遍歷數組，如果當前的數num[i]，

如果num[i]<=0或者num[i]超過了n，則第一個丟掉的整數必然在num[i]的前面，將num[i]和num[n-1]互換，n--；

如果1<=num[i]<=n,表明這個數可能是好的，將他放在正確的位置swap(num[i],num[num[i]-1])

如果num[i]==i+1,則表明該數字在正確的位置，i++

class Solution {
public:int firstMissingPositive(int A[], int n) {int m = n;for(int i=0;i<m;i++){if(A[i] == i+1)continue;else{if(A[i] > m || A[i] == 0 || A[i] < 0 || A[i] <= i){if(i==m-1)return m;swap(A[i],A[m-1]);m--;i--;}else{if(A[i] == A[A[i]-1]){swap(A[i],A[m-1]);m--;i--;}else{swap(A[i],A[A[i]-1]);i--;}}}}return m+1;}
};

?