Find out the smallest positive integer that is not in the given array

Problem:  Given is an unsorted integer array, find out the smallest positive integer that is not in this array.

Example: {1,3,4, 6}  => 2.   {0,2,5,4}  => 1. {1,2,3} =>4.  {-2,5,2,1} =>3

Becareful: The array may contain negative integer, and 0 is a possible trouble maker.

Time&Space requirement: O(n) and O(1)

————————————————————————————————————————-

Solution: 

For each element in the array, try to put it into the array if it is a positive integer. More specifically, if this element num satisfies 0 < num< arraySize, then it should be put into array[num]. If either arraySize < num or num < 0 observed, it is left unchanged.

In this manner, after we go through the array once, in an ideal case the array[0] should be 1, array[1] should be 2 …. and so on. If we find array[num] != num – 1, then num is the smallest positive integer that is not in the array. If we observe array[num] == num-1 for all 0 < num< arraySize, then num+1 is the smallest positive integer that we are looking for.

We use only O(1) space to do the switches, and every element in this array is switched for at most twice, therefore, the time complexity is O(n)

Test cases:

{3,5,1,2,7,6,4},  {2,1,3},  {0,2,1,3} , {0,1,1,1,2,3}, {-5,2,-1,1,3,4}

public static void array_FindOutSmallestPositiveThatIsNotInTheArray(int [] num){
        for(int i=0;i<num.length;i++){
            int index = i;
            while(num[index] >0 && num[index] < num.length &&
              num[index] - 1 != index && num[index]!=num[num[index]-1]){
                int temp = num[num[index]-1];
                num[num[index]-1] = num[index];
                num[index] = temp;
            }
        }
        for(int i=0;i<num.length;i++)
            if(num[i]-1 != i){
                System.out.println( i + 1 );
                return;
            }
        System.out.println(num.length + 1);
    }