41、First Missing Positive 问题

problem：

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

For example,Given[1,2,0]return3,and[3,4,-1,1]return2.

Your algorithm should run inO(n) time and uses constant space.

题意为，按顺序找第一个缺失的正整数

thinking：

如果不要求O（n）的时间复杂度，hash table和 排序都可以很简单解决。

code：

class Solution{public:int firstMissingPositive(int A[], int n){int i = 0;for (; i < n; ){if (A[i] <= 0 || A[i] == i+1 || A[i] > n || A[i] == A[A[i]-1]) i++; // 无效交换或位置正确else swap(A[i], A[A[i]-1]); // 交换到正确的位置上}for (i = 0; i < n; i++) if (A[i] != i+1) break; // 寻找第一个丢失的正数return i+1;}};

，人生伟业的建立，不在能知，乃在能行。