First Missing Positive 189

Question

Solution

Idea: 数组第x位上的数字应该是x+1。遍历数组，将每一个数送到它应该在的位置上。然后再次遍历新数组，找到第一个第x位上不等于x＋1的数。将数组元素调整到其应该在的位置上的具体操作如下：

1) 遍历数组，在第i位时，若为正数且数值小于A.length且第i位上的数不等于i+1时，可以将该位上的数调整到其应该在的位置。根据第x位的数应该为x+1的规则，则该位上的数应该在的位置为A[i]-1。这里详细说一下，若该位为负数或数值大于A.length则得到其应该在的位置，所以无法调整，继续下一个数。

2) 看其应该在的位置上（A[i]-1）的数是否为正确的数（A[i]），若已经正确，则无需调整，否则将第i位数与第A[i]-1位数进行互换。对新换到i位上的数重复上述步骤。（因此要用while）

3) 遍历整个数组则所有能调整的数都已经被调整到其合适的位置上

4) 再次遍历数组，找到第一个第x位上不等于x＋1的数并返回x+1

代码如下：

public class Solution {
    /**    
     * @param A: an array of integers
     * @return: an integer
     */
    public int firstMissingPositive(int[] A) {
        // write your code here
        if(A == null || A.length == 0){
            return 1;
        }

        for(int i = 0; i < A.length; i++){
            while(A[i] > 0 && A[i] != (i + 1) && A[i] <= A.length){
                int index = A[i] - 1;
                if(A[index] == A[i]){
                    break;
                }
                int temp = A[i];
                A[i] = A[index];
                A[index] = temp;
            }
        }

        for(int i = 0; i < A.length; i++){
            if(A[i] != i + 1){
                return i + 1;
            }
        }

        return A.length + 1;
    }
}