[LeetCode]41.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.

【分析】

类似于桶排序。

每当A[i] != i+1时,即A[i]不在正确的位置上，需要交换到排序数组中他相应的位置上去。

交换A[i]与A[A[i]-1],直到无法交换。

【代码】

/*********************************
*   日期：2015-01-13
*   作者：SJF0115
*   题目: 41.First Missing Positive
*   来源：https://oj.leetcode.com/problems/first-missing-positive/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
using namespace std;

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        if(A == NULL || n <= 0){
            return 1;
        }//if
        // 交换到在排序数组中应有的位置
        for(int i = 0;i < n;i++){
            // 交换直到不能交换
            while(A[i] != i+1){
                // 是否需要交换
                if(A[i] <= 0 || A[i] > n || A[i] == i+1 || A[i] == A[A[i]-1]){
                    break;
                }//if
                // 交换
                int tmp = A[i];
                A[i] = A[tmp-1];
                A[tmp-1] = tmp;
            }//while
        }//for
        // First Missing Positive
        for(int i = 0;i < n;i++){
            if(A[i] != i+1){
                return i+1;
            }//if
        }//for
        return n+1;
    }
};

int main(){
    Solution solution;
    int A[] = {1,1};
    cout<<solution.firstMissingPositive(A,2)<<endl;
    return 0;
}

【分析二】

题目的最后一行，要求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) {
        if(A == NULL || n <= 0){
            return 1;
        }//if
        int impossValue = n + 2;
        //first run, turn every negetive value into an impossible positive value
        //make every value in A is positive
        for(int i = 0;i < n;i++){
            if(A[i] <= 0){
                A[i] = impossValue;
            }//if
        }//for
        //second run, make A[] as a hash table, A[i] indicate the presence of i + 1
        //the way is that, if k in [1,n] is in A[], then turn A[k -1] to negetive
        for(int i = 0;i < n;i++){
            int value = abs(A[i]);
            if(value <= n){
                A[value-1] = -abs(A[value-1]);
            }//if
        }//for
        //third run, if A[i] is positive, from step 2, we know that i + 1 is missing.
        for(int i = 0;i < n;i++){
            if(A[i] > 0){
                return i+1;
            }//if
        }//for
        //all int from 1 to n is present, then return n + 1
        return n+1;
    }
};