Description
Given an unsorted integer array, find the first missing positive integer.
Your algorithm should run in O(n) time and uses constant space.
Example
Given [1,2,0] return 3, and [3,4,-1,1] return 2.
Discussion
给定一个未排序的数组，找出第一个缺失的正整数的位置。
由于额外空间要求是常数空间。因此我们需要在原数组上进行修改。从前向后遍历数组，如果当前数字不应该在这个位置上，就把它与它应该在的位置上的数字进行交换。如果这两个数字相同则跳过，否则会进入无限循环。
算法的时间复杂度为O(n)。
C++ Code
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
if(nums.size() == 0)
{
return 1;
}
int pos = 0;
while(pos < nums.size())
{
if(nums[pos] != pos + 1 && nums[pos] > 0 && nums[pos] < nums.size() + 1 && nums[pos] != nums[nums[pos] - 1])
{
swap(nums[pos], nums[nums[pos] - 1]); //将当前数字与该数字应该在的位置上的数字进行交换
}
else
{
pos ++;
}
}
//循环查找第一个丢掉的正整数
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] != i + 1)
{
return i + 1;
}
}
return nums.size() + 1;
}
};