**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

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;
}
};