首页 > 代码库 > [LeetCode] [First Missing Positive 2012-03-08]

[LeetCode] [First Missing Positive 2012-03-08]

2024-07-07 23:42:12   214人阅读

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
     
    void LinkMove(int A[], int i, int n)
    {
        if(A[i] > n || A[i] <= 0)   
        {
            A[i] = -1;
            return;
        }
        if(A[i] == i+1)   return;
         
        int s = A[i]-1;
         
        int tmp = A[s];
        A[s] = A[i];
        A[i] = tmp;
        if(A[s] != A[i] ) //should be check, or there will be a circle call
        {
            LinkMove(A, i, n);
        }
    }
    int firstMissingPositive(int A[], int n) {
        for(int i = 0;i<n;i++)
        {
            LinkMove(A, i, n);
        }
        for(int i = 0; i< n; i++)
        {
            if(A[i] <= 0 || A[i] != i+1) return i+1; 
        }
        return n+1;
    }
};

 


联系
我们