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.

 

题解：这道题目比较简单，需要注意的是几个陷阱：数组为空，数组里数据重复。

比较有技巧的地方是O(1)space，因为考虑到数据重复，此处只能排序， 这就要求重用nums数组空间。

引用网上一位网友的题解：

Put each number in its right place.For example:When we find 5, then swap it with A[4].At last, the first place where its number is not right, return the place + 1.

程序：

1 class Solution { 2 public: 3     int firstMissingPositive(vector
     
      & nums) { 4         for (int i = 0; i < nums.size(); i++) 5         { 6             while (nums[i] > 0 && nums[i] <= nums.size() && nums[i] != nums[nums[i] -1]) 7             { 8                 swap(nums[i], nums[nums[i] -1]); 9             }10         }11         for (int i = 0; i < nums.size(); i++)12         {13             if (nums[i] != i + 1)14             {15                 return i + 1;16             }17         }18         return nums.size() + 1;19     }20 };