Problem

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]

Input: [3,4,-1,1]

Input: [7,8,9,11,12]

Your algorithm should run in O(n) time and uses constant extra space.

Solution

class Solution {    public int firstMissingPositive(int[] A) {        int i = 0;        while(i < A.length){            //we want every A[i] = i+1, so we can find the first missing one            //if A[i] is negative or out of scope, or it's in desired position, continue            if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++;            //if the number at the desired position of A[i] isn't A[i], swap them            else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);            //otherwise, A[A[i]-1] == A[i], we have a duplicate, move on            else i++;        }                //now check from the beginning        i = 0;        while(i < A.length && A[i] == i+1) i++;        return i+1;    }        private void swap(int[] A, int i, int j){        int temp = A[i];        A[i] = A[j];        A[j] = temp;    }}