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 }

 

Link of this Article: First Missing Positive

Leave a Reply

Your email address will not be published. Required fields are marked *