題目

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] 交換到 A[A[i] - 1]中，需要注意臨界條件。PS：直接hash太浪費空間。

    public int firstMissingPositive(int[] A) {
        int len = A.length;
        for (int i = 0; i < len; ) {
        	if (A[i] > 0) {
            	if (A[i] < len && A[i] != i + 1 && A[i] != A[A[i] - 1]) {
            		int tempOne = A[i];
            		int tempTwo = A[A[i] - 1];
            		A[i] = tempTwo;           		
            		A[tempOne - 1] = tempOne;
            	} else {
            		i++;
            	}
        	} else {
        		i++;
        	}

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