本文共 1010 字，大约阅读时间需要 3 分钟。

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.

Java代码：

public class Solution {   public int firstMissingPositive(int[] A) {    if (A == null || A.length == 0) {        return 1;    }    // Put the corresponding positive value in the index that equals to its value    int len = A.length;    for (int i = 0; i < len;) {        int num = A[i];        if (num > 0 && num < len && num != i && num != A[num]) {            A[i] = A[num];            A[num] = num;        } else {            ++i;        }    }    // Scan the array to find the first value that is not equal to its index, then it is the missing value    // Test small examples first    int missingValue = A[0] == len ? len+1 : len;    for (int i = 1; i < len; ++i) {        if (A[i] != i) {            missingValue = i;            break;        }    }    return missingValue;}}

转载地址：http://csuni.baihongyu.com/