First Missing Positive

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

Analyse:

1. Newest method: 0ms

 1 class Solution {
 2 public:
 3     int firstMissingPositive(vector<int>& nums) {
 4         if(nums.empty()) return 1;
 5 
 6         nums.push_back(-1);
 7         for(int i = 0; i < nums.size(); i++){
 8             while(nums[i] > 0 && nums[i] < nums.size() && i < nums.size()) {
 9                 if(nums[i] != i && nums[i] != nums[nums[i]])
10                     swap(nums[nums[i]], nums[i]);
11                 else i++;
12             }
13         }
14         for(int i = 1; i < nums.size(); i++){
15             if(nums[i] != i) return i;
16         }
17         return nums.size();
18     }
19 };

2. Old method

class Solution {
public:
    // Create a new vector of size nums.size()
    // Ignore the negative values and values larger than nums.size()
    // Put corresponding numbers in the array 
    // Scan the array for the second time
    int firstMissingPositive(vector<int>& nums) {
        if(nums.empty()) return 1;
        
        int n = nums.size();
        vector<int> temp(n + 1, 0); // Index start from 0
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] < 0 || nums[i] > n) 
                continue;
            temp[nums[i]] = nums[i];
        }
        for(int i = 1; i <= n + 1; i++){
            if(temp[i] == 0) return i;
        }
        return n + 1;
    }
};