Category:ACM_LeetcodeS

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