41. First Missing Positive

Description:

https://leetcode.com/problems/first-missing-positive/#/description

Algorithm:

I used unordered_map.

Go through the array to record the max number and min number.

 

Code:

class Solution {
public:
int firstMissingPositive(vector& nums) {
unordered_map <int, int> mapping;
int maxNum = 0;
int minNum = INT_MAX;
for (int i = 0; i < nums.size(); i++) { mapping[nums[i]] = 1; if (nums[i] > maxNum)
maxNum = nums[i];
if (nums[i] < minNum)
minNum = nums[i];
}
if (maxNum < 1 || minNum > 1) return 1;
for (int i = 1; i < maxNum; i++)
{
auto it2 = mapping.find(i);
if (it2 == mapping.end())
return i;
}
return maxNum + 1;
}
};

 

Timing:

Beats 2.82% (:( ) 9ms

Best 3ms code:

 

class Solution {
public:
int firstMissingPositive(vector& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) { while (nums[i] != i + 1) { if (nums[i] <= 0 || nums[i] > n || nums[i] == nums[nums[i] - 1]) break;
swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = 0; i < n; i++) { if (nums[i] != i + 1) return i + 1; } return n + 1; } };