Article From:https://www.cnblogs.com/guxuanqing/p/9063310.html

41. First Missing Positive

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

Example 1:

```Input: [1,2,0]
Output: 3
```

Example 2:

```Input: [3,4,-1,1]
Output: 2
```

Example 3:

```Input: [7,8,9,11,12]
Output: 1
```

Note:

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

The idea of solving the problem:

The first step is to make an hash map of the integer greater than 0 in the array and get the maximum ARRMAX at the same time.

The second step: from 1 to ARRMAX traversing the hash table, find the first termination for 0, return to find the index value finally.

``` 1 #define HASHNUM 100000
2
3 int firstMissingPositive(int* nums, int numsSize)
4 {
5     int numsMax = 0;
6     int hash[HASHNUM] = {0};
7     // hash and seek for array max num.
8     for(int idx = 0; idx < numsSize; ++idx)
9     {
10         if(nums[idx] <= 0 ) continue;
11         else
12         {
13             hash[nums[idx]] = 1;
14             if(numsMax < nums[idx])
15             {
16                 numsMax = nums[idx];
17             }
18         }
19     }
20
21     // judge for missing
22     int retIdx = 1;
23     for(retIdx = 1; retIdx <= numsMax; ++retIdx)
24     {
25         if(hash[retIdx] == 0)
26         {
27             break;
28         }
29     }
30
31     return retIdx;
32 }```