Given an unsorted integer array, find the first missing positive integer.

For example,

Given

and

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.

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.

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; } };

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

ReplyDeletewhile (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]))吗？

谢谢你的代码！

Hi there,

DeleteI'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!

谢谢你的详细解答，但我觉得这种情况是只有在array里有duplicate的时候才需要考虑

ReplyDelete比如说

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吗？

谢谢！

btw, I want to say I really like your post on sorting algorithms. Very clear and informative!

ReplyDelete牛人，点赞没商量！