【LeetCode】41. First Missing Positive (3 solutions)

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

    }

};

巴特西

【LeetCode】41. First Missing Positive (3 solutions)

最新文章

热门文章