First Missing Positive
最后更新于：2022-04-01 22:58:03
**一. 题目描述**
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.
**二. 题目分析**
该题的大意是给定一个未排序的数组，该数组可能包含零或正负数，要求找出第一个未出现的正数。例如`[1, 2, 0]`，由于第一个未出现的正整数是`3`，则返回`3`；`[3, 4, -1, 1]`第一个未出现的正整数是`2`，则返回`2`。算法要求在`O(n)`的时间复杂度及常数空间复杂度内完成。
一种方法是，先把数组里每个正整数从`i`位放到第`i-1`位上，这样就形成了有序的序列，然后检查每一下标`index`与当前元素值，就能知道当前下标所对应的正整数是否缺失，若缺失则返回下标`index + 1`即可。
**三. 示例代码**
~~~
#include
#include
using namespace std;
class Solution
{
public:
int firstMissingPositive(vector& nums)
{
int n = nums.size();
for (int i = 0; i < n; ++i)
{
int temp = 0;
while (i + 1 != nums[i] && nums[i] != nums[nums[i] - 1] && nums[i] > 0)
{
temp = nums[i];
nums[i] = nums[temp - 1];
nums[temp - 1] = temp;
}
}
for (int i = 0; i < n; ++i)
{
if (i + 1 != nums[i])
return i + 1;
}
return n + 1;
}
};
~~~
';