# 41 - First Missing Positive

解法一 - 不管題目限制，用 set 儲存出現過的 int

從 1 往上看到最大的 element+1，第一個不在 set 中的就是答案。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        if(nums.empty()) return 1;

        // store in set
        set<int> s;
        for(int i=0; i<nums.size(); i++) {
            s.insert(nums[i]);
        }

        // find the max element in nums
        auto maxNum = max_element(nums.begin(), nums.end());

        // go through each in table
        int i;
        for(i=1; i<*maxNum+1; i++){
            if(s.find(i) == s.end())
                break;
        }

        return i;
    }
};

解法二 - 利用 array 的 index 來表示 i-th positive int 在不在

這個解法的主要概念有兩個：

1. 如果 nums 的大小是 n，first missing positive int 最大只能是 n+1。

2. 我們可以用 nums[1] 的值表示 1 這個 int 在不在，nums[2] 表示 2 在不在...nums[0] 表示 n 在不在。

實作如下：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 1;

        int countOne = 0;
        for(int i=0; i<n; i++) {
            if(nums[i] == 1) {
                countOne++;
                break;
            }
        }

        if(countOne == 0)
            return 1;

        if(n == 1)
            return 2;

        for(int i=0; i<n; i++) {
            if(nums[i] <= 0 || nums[i] > n)
                nums[i] = 1;
        }

        for(int i=0; i<n; i++) {
            int index = abs(nums[i]);

            if(index == n)
                nums[0] *= -1;
            else {
                if(nums[index] > 0)
                    nums[index] *= -1;
            }    
        }


        int i;
        for(i=1; i<n; i++) {
            if(nums[i] > 0)
                return i;
        }

        if(nums[0] > 0) return n;

        return n+1;
    }
};