leetcode Question 29: First Missing Positive

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.

Analysis:

If we can use another array flag, we can assign flag[A[i]-1] = A[i] to present its occurrence.And get the first element from flag that the flag[i-1]!=i as the result. Here A[i]-1 and i-1 because the array is from 0 to n-1 to store 1 to n.
But the question requires that we can not use additional space. So we have to use the original array A, to save the flag.
The idea is as follow:
e.g. 3,2,5,1,7
For each element,
1. Do not consider the element which <=0, or value > length n
2. Swap this element A[i] with the A[A[i]-1], e.g. when we met A[0]=3, we swap A[0] and A[2], then A[0]=5
3. For the current element A[i], if A[i]<=0 or A[i]>length n, or A[i] has already occurred, break. Else go to step 2.
e.g. A[0]=5, swap A[0] and A[5], A[0]=7, break.Now the array A is {7,2,3,1,5}.
Next round, A is {1,2,3,7,5}
4. Scan the array A and find the result. e.g. {1,2,3,7,5}, the A[3]!=3+1, print 3+1, result =4.

Source code:

class Solution {
public:
int firstMissingPositive(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
for (int i = 0; i<n;i++){
if ( (A[i]>0)&&(A[i]<=n)){
while (A[i]!=(i+1)){
if ((A[i]>n)||(A[i]<=0)||(A[A[i]-1]==A[i])) {break;}
int tmp;
tmp = A[A[i]-1];
A[A[i]-1]=A[i];
A[i]=tmp;
}
}
}

int i=0;
for (; i<n;i++){
if (A[i]!=(i+1)){
return i+1;
}
}
return i+1;

}
};


1. 你好，我想和你讨论一下你的一行code

while (A[i]!=(i+1)){
if ((A[i]>n)||(A[i]<=0)||(A[A[i]-1]==A[i])) {break;}

你写的break的条件有三个，前两个我明白，最后一个(A[A[i]-1]==A[i]))其实不就是A[i]==(i+1)吗？如果这个条件成立，外循环的while就不会execute，直接进入下一个i了。。
我的意思是，有了while (A[i]!=(i+1))，还需要(A[A[i]-1]==A[i]))吗？

谢谢你的代码！

1. Hi there,
I've checked the code again, and the 3rd condition in the "if " is required.
As I said in the post (3rd point),"For the current element A[i], if A[i]<=0 or A[i]>length n, or A[i] has already occurred, break"

The A[A[i]-1]==A[i] check if the element has already occurred.

Also, A[i]==i+1 does not mean A[A[i]-1]==A[i], the first one check if the current element on the current position is correct, the second check if the current value has occurred. e.g.
Let's say A=[1,1], i=1
So, A[i]==i+1 --> A[1]==2 ---> 1==2 ---> false
A[A[i]-1]==A[i] --> A[A[1]-1]==A[1] --> A[0]==A[1] --> 1==1 ---> true

I want to also mention that you can have some modifications on the code to make it clearer, when you do that, pay attention to the starting case (A[0]), and the case that array has duplicate numbers.

Thanks!

2. 谢谢你的详细解答，但我觉得这种情况是只有在array里有duplicate的时候才需要考虑
比如说
A[] = {1,2,3,4,5，2}
前面的都没问题，又碰到第二个2的时候，A[i]!=i+1,就是说2不在正确的位置上，需要swap;
下一步我们看2应该在的位置也就是A[1]是不是已经被2占了，也就是说，A[A[i]-1]==A[i]
那么我们发现A[1]=2, 所以不必swap, break出来。
这应该是个很好的检查是不是有array是不是有duplicate的元素。但如果array都是unique的话，还需要这个check吗？

谢谢！

3. btw, I want to say I really like your post on sorting algorithms. Very clear and informative!
牛人，点赞没商量！