【leetcode】 First Missing Positive

地址

https://leetcode.com/problems/first-missing-positive/description/

题目

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,然后从1开始扫到的第一个为0的位置即是答案。 有空间限制的话,借助上面的思路,把题目所给的数组当作标记数组应用即可。下面举例说明做法: 假如有数组a[4,5,3,2,6],从左向右扫到第一个数4,那么把a[4]位置打个标记让a[4]=flag,同时取出原a[4]上的数2。重复同样的工作,让a[2]=flag,然后从原a[2]的数5继续开始,让a[5]=flag,之后因为原a[5]:6大于数组大小5所以不管。 这样一轮之后数组a变成了[4,flag,3,flag,flag],然后从下一个非flag数3重复上面的算法,最后得到[4,flag,flag,flag,flag]。最后第一个非flag位置即是第一个没出现的数,如果数组中不存在不是flag的位置,那么size(a)+1就是第一个没出现的数。 这题有非正数,遇到非正数时直接跳过即可,flag用一个不会出现的数表示比如-1e9-7。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int firstMissingPositive(vector<int>& num) {
int ff=-1e9-7,n=num.size(),ans=n+1;
for(int i=0;i<n;i++)
if(num[i]<=0)
continue;
else
{
for(int j=num[i],t;j>0&&j<=n;t=num[j-1],num[j-1]=ff,j=t)
;
}
for(int i=0;i<n;i++)
if(num[i]!=ff)
{
ans=i+1;
break;
}
return ans;
}
};