Description

You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space. You can modify the original array.

Example

Input:  {2, 3, 7, 6, 8, -1, -10, 15}
Output: 1
Input:  { 2, 3, -7, 6, 8, 1, -10, 15 }
Output: 4
Input: {1, 1, 0, -1, -2}
Output: 2

Solution

1. sort
2. hashmap，key是所有的positive number O(n) time O(1) space. 如果数组中全是正数，遍历数组，遇到value为v的数，把index为v-1的位置上的数标成负数。遇到的value可能是负数（已经被标记过了），去他的绝对值即可。最后重新遍历一遍数组，找到第一个不未负的数即为连续数列中缺失的数。 这道题中因为包括正数和非整数，故先做一个处理，把所有的正数放到前面，非整数放到后面，可以有pivot=0来partition这个数组。之后对前面正数位的数采用以上方法处理即可。