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.

http://www.lintcode.com/en/problem/first-missing-positive/

https://leetcode.com/problems/first-missing-positive/

Discussion

因为要去O(n) time，常规排序算法是不行了，最快的快速排序还要O(n logn)。而线性排序的算法就要考虑桶排序了。它的核心思想是sorted[unsorted[i]] = unsorted[i].这是一篇介绍桶排序的文章。 以下是我自己的实现。

Solution 1

class Solution {
public:
    /**    
     * @param A: a vector of integers
     * @return: an integer
     */
    int firstMissingPositive(vector<int> A) {
        // write your code here
        int i = 0;
        int n = A.size();
        vector<int> B(n, -1);
        for (int i = 0; i < n; i++) {
            if (A[i] > 0 && A[i] <= n) {
                B[A[i]-1] = A[i];
            }
        }
        for (int i = 0; i < n; i++) {
            if (B[i] != i + 1)
                return i + 1;
        }
        return n+1;
    }
};

上面的解法是 O(n) space。题目要求constant space，因为本身A是只有一个positive number missing的，所以利用A本身就可以，保证当A[i] ！= i+1的时候，不是B[A[i]-1] = A[i],二十交换A[i] and A[A[i]-1].

Solutioin 2

class Solution {
public:
    /**    
     * @param A: a vector of integers
     * @return: an integer
     */
    int firstMissingPositive(vector<int> A) {
        // write your code here
        int i=0; 
        while (i<A.size()) {
            if(A[i] == i+1 || A[i]<=0 || A[i]>A.size() || A[i] == A[A[i]-1]) {
                i++;
            } else {
                int tmp = A[i];
                A[i] = A[A[i]-1];
                A[tmp-1] = tmp;//不能是A[A[i]-1]=tmp,因为A[i]已经update了
                //swap(A[i], A[A[i]-1]);//用swap是一个安全的选择
            }
        }
        for(int i=0; i<A.size(); i++) {
            if(A[i] != i+1)
                return i+1;
        }
        return A.size()+1;
    }
};

class Solution {
public:
    /**    
     * @param A: a vector of integers
     * @return: an integer
     */
    int firstMissingPositive(vector<int> A) {
        // write your code here
        int n = A.size();
        for(int i=0; i<n; i++) {
            while (i+1 != A[i]) {//一直交换知道满足条件或者break
                if(A[i] <=0 || A[i] >n || A[A[i]-1] == A[i] )
                    break;
                swap(A[A[i]-1], A[i]);
            } 
        }
        for (int i=0; i<n; i++) {
            if(A[i] != i+1) {
                return i+1;
            }
        }
        return n+1;
    }
};