# 41 - First Missing Positive

解法一 - Cyclic sort

這題如果不會 cyclic sort，真的是有一點複雜，滿容易出錯。但如果會 cyclic sort，只要先做完 cyclic sort，第一個跟 index 對不上的地方就是 missing 的 positive。

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

        // Cyclic sort
        int i = 0, n = nums.size();
        while(i < n) {
            int j = nums[i] - 1;

            if(j >= 0 and j < n and nums[i] != nums[j]) {
                swap(nums[i], nums[j]);
            }
            else{
                ++i;
            }
        }

        // Find the first idx not matching with nums[idx]
        for(int i = 0; i < n; ++i) {
            if(nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
};

上面這個實作會掛在一些 edge case，例如 array 裡面有 INT_MIN，那再算 j 的時候就會出錯，不過面試時應該實作出上面那種就可以。

附上可以過 leetcode 的版本：

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

        // Cyclic sort
        int i = 0, n = nums.size();
        while(i < n) {
            if(nums[i] == INT_MIN) {
                ++i;
                continue;
            }
            int j = nums[i] - 1;

            if(j >= 0 and j < n and nums[i] != nums[j]) {
                swap(nums[i], nums[j]);
            }
            else{
                ++i;
            }
        }

        // Find the first idx not matching with nums[idx]
        for(int i = 0; i < n; ++i) {
            if(nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
};