Simple O(n) JAVA solution based on Bucket Sort


  • 1

    Explanation

    The basic idea is from bucket sort, which means putting every element A[i] to the position A[i] - 1, and then check the positive integer from position 0.

    public int firstMissingPositive(int A[]) {
    	for (int i = 0; i < A.length; i++) {
    		int desired = A[i] - 1; 
    		// Set A[i] to position A[i] - 1. A[i] equals A[desired] will cause endless loop.
    		if (desired >= 0 && desired < A.length && desired != i && A[i] != A[desired]) {
    			swap(A, i, desired); i--;
    		}
    	}		
        // Find the first missing positive integer.
    	for (int i = 0; i < A.length; i++) 
    		if (A[i] != i + 1) return i + 1;
    	return A.length + 1;
    }
    	
    void swap(int[] A, int i, int j) {
    	 int tmp = A[i]; A[i] = A[j];  A[j] = tmp;
    }

  • 0
    L
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.