First Missing Positive
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(nlogn) time and O(1) space
无脑解法-->先排序O(nlogn)
思想如下：
1、略去非正的前缀数。
2、记下一个待匹配的正整数为tag。
考虑重复，如果A[i]等于tag，则tag++
如果A[i]大于tag，则返回tag
A[i]不可能小于tag，由排序可以保证。
class Solution {
public:
int firstMissingPositive(int A[], int n) {
if(n == )
return ;
sort(A,A+n);
int i = ;
while(i < n && A[i] <= )
i ++;
if(i == n)
return ;
int tag = ;
for(; i < n; i ++)
{
if(A[i] > tag)
//miss the tag
return tag;
else if(A[i] == tag)
//next positive
tag ++;
else
;
}
//i==n, miss the tag
return tag;
}
};
解法二：O(n) time and O(n) space
稍作思考就可以知道，n容量的数组，最多覆盖的正整数为连续的1~n
也就是说，丢失的正整数要么出现在1~n中，要么就是n+1
因此可以构造大小为n的数组v，v[i]记录i+1这个数字是否出现在A中。
如果tag全true则返回n+1，否则返回第一个tag为负的下标+1
class Solution {
public:
int firstMissingPositive(int A[], int n) {
if(n == )
return ;
//tag[i] means whether i+1 exists in A
//at most 1~n, then return n+1
vector<bool> tag(n, false);
for(int i = ; i < n; i ++)
{
if(A[i] > && A[i] <= n)
tag[A[i]-] = true;
}
for(int i = ; i < n; i ++)
{
if(tag[i] == false)
return i+;
}
return n+;
}
};
解法三：O(n) time and O(1) space
解法二中我们构建了新的数组tag来记录每个正整数是否出现在A中，
其实可以省略tag数组，直接在A中记录。这点借鉴了yuyibestman想法。
具体做法为，先将A划分为正整数与非负数。这点类似快排的partition。
A[i]的正负号记录i+1这个数字是否出现在A中。
由于只是符号取负，其值可以通过绝对值函数恢复。这样就代替了解法二中的tag数组了。
class Solution {
public:
int firstMissingPositive(int A[], int n) {
if(n == )
return ;
//if A[i] is negative, i+1 exists in original A
//partition, non-negative only
int low = ;
int high = n-;
int end = n-;
while(low <= high)
{
while(low <= high && A[low] > )
low ++;
//to here,
//case low > high: partition finished, high point to the end of the new array
if(low > high)
{
end = high;
break;
}
//case A[low]<=0: low point to the first non-positive element
while(high >= low && A[high] <= )
high --;
//to here,
//case high < low: partition finished, high point to the end of the new array
if(low > high)
{
end = high;
break;
}
//case A[high]>0: high point to the first positive element
swap(A[low],A[high]);
}
for(int i = ; i <= end; i ++)
{
//check whether num is in A, and set A[num-1] to be negative
int num = abs(A[i]);
if(num <= end+)
{
if(A[num-] > )
A[num-] *= -;
}
//out of range 1~end+1
}
for(int i = ; i <= end; i ++)
{
if(A[i] > )
return i+;
}
return end+;
}
};