LeetCode OJ:First Missing Positive

1、不考虑时间复杂度，可以用排序做，时间复杂度为O(logn)

排序版，12ms过

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        sort(A,A+n);
        int cnt=0;
        for(int i=0;i<n;i++){
            if(A[i]<=cnt)continue;
            cnt++;
            if(cnt!=A[i])return cnt;
        }
        return cnt+1;
    }
};

12ms过

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        vector<bool> B(n+1,0);
        for(int i=0;i<n;i++){
            if(A[i]<=0)continue;
            B[A[i]]=1;
        }
        for(int i=1;i<=n;i++){
            if(!B[i])return i;
        }
        return n+1;
    }
};

3、题目的最后一行，要求O(n)实际上暗示了用hash，但是又说要contant space，就没法再开新空间来建hash。
正好这个题目中处理的是1到n的数据，提供了一个将输入的数组同时用作hash表的可能性。
于是算法就是：

1. 第一遍扫描排除所有非正的数，将它们设为一个无关紧要的正数(n+2)，因为n+2不可能是答案
2. 第二遍扫描，将数组作为hash表来使用，用数的正负来表示一个数是否存在在A[]中。
   当遇到A[i]，而A[i]属于区间[1,n]，就把A中位于此位置A[i] – 1的数置翻转为负数。
   所以我们取一个A[i]的时候，要取它的abs，因为如果它是负数的话，通过步骤一之后，只可能是我们主动设置成负数的
3. 第三遍扫描，如果遇到一个A[i]是正数，说明i+1这个数没有出现在A[]中，只需要返回即可。
4. 上一步没返回，说明1到n都在，那就返回n+1

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for(int i=0;i<n;i++)if(A[i]<=0)A[i]=INT_MAX;
        for(int i=0;i<n;i++){
            int a=abs(A[i]);
            if(a<=n)
                A[a-1]=-abs(A[a-1]);
        }
        for(int i=0;i<n;i++)
            if(A[i]>0)return i+1;
        return n+1;
    }
};

LeetCode OJ:First Missing Positive

原文：http://blog.csdn.net/starcuan/article/details/18865515