41. First Missing Positive

分为N内缺数和不缺(返回N-1)。因为是有序的，检查N内是否缺可以开辟一个长度为N的bool数组mark，在遍历nums时遇到的正整数就在mark中标上。然后再遍历mark找到第一个为false的元素。由于我们要找的是正整数，其实可以在原数组上用取负作为mark数组用。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        const int N = nums.size();
        for (auto &num : nums) {
            if (num <= 0) num = INT_MAX;
        }
        for (auto num : nums) {
            num = abs(num);
            if (num <= N) nums[num - 1] = -abs(nums[num - 1]);
        }
        for (int i = 0; i < N; ++i) {
            if (nums[i] >= 0) return i + 1;
        }
        return N + 1;
    }
};