leetcode: First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
Your algorithm should run in O(n) time and uses constant space.
Solution and Precautions:
Linear time usually requires hash table to do search in constant time, constant space requires we use a fixed number of variables or we directly use the input memory. Here constant space means the second case. So basically we use the input array A as our hash table, and by one pass through the whole array, we put each number a >= 1 and a <= n into the right position, that is a should be in position a-1, the key observation is that, the first missing positive could only be 1,….n, n+1, so basically we try to set all these positions in A to contain the right number, after this is done, we check the first slot where the position does not contain the right number, this position + 1 is the first missing positive. We can use swap or something else to do the thing that we set the position to contain the right number.