Smallest missing integer algorithm that runs in O(n)?

The smallest missing integer must be in the range [1, ..., n+1]. So create an array of flags, all initially false, indicating the presence of that integer. Then an algorithm is:

1. Scan the input array, setting flags to true as you encounter values in the range. This operation is O(n). (That is, set flag[A[i]] to true for each position i in the input array, provided A[i] <= n.)
2. Scan the flag array for the first false flag. This operation is also O(n). The index of the first false flag is the smallest missing integer.

EDIT: O(n) time algorithm with O(1) extra space:

If A is writable and there are some extra bits available in the elements of A, then a constant-extra-space algorithm is possible. For instance, if the elements of A are signed values, and since all the numbers are positive, we can use the sign bit of the numbers in the original array as the flags, rather than creating a new flag array. So the algorithm would be:

1. For each position i of the original array, if abs(A[i]) < n+1, make the value at A[abs(A[i])] negative. (This assumes array indexes are based at 1. Adjust in the obvious way if you are using 0-based arrays.) Don't just negate the value, in case there are duplicate values in A.
2. Find the index of the first element of A that is positive. That index is the smallest missing number in A. If all positions are negative, then A must be a permutation of {1, ..., n} and hence the smallest missing number is n+1.

If the elements are unsigned, but can hold values as high as 4 n + 1, then in step 1, instead of making the element negative, add 2 n + 1 (provided the element is <= 2 n) and use (A[i] mod (2n+1)) instead of abs(A[i]). Then in step 2, find the first element < 2 n + 1 instead of the first positive element. Other such tricks are possible as well.

An implementation of Paul Hankin's idea in C++

#include <iostream>
using namespace std;
const int MAX = 1000;
int a[MAX];
int n;

void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

// Rearranges elements of a[l..r] in such a way that first come elements 
// lower or equal to M, next come elements greater than M. Elements in each group
// come in no particular order.
// Returns an index of the first element among a[l..r] which is greater than M.
int rearrange(int l, int r, int M) {
    int i = l, j = r;
    while (i <= j)
        if (a[i] <= M) i++;
        else swap(a[i], a[j--]);
    return i;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int L = 1, R = 2 * n;
    int l = 0, r = n - 1;
    while (L < R) {
        int M = (L + R) / 2; // pivot element
        int m = rearrange(l, r, M); 
        if (m - l == M - L + 1) 
            l = m, L = M + 1;
        else
            r = m - 1, R = M;
    }

    cout << L;
    return 0;
}