[c++] 41. First Missing Positive

Set을 이용하면 쉽게 풀 수 있지만, 문제에서는 constant space만 사용하라고 되어있다. 
n에 의해서 크기가 변화되는, 즉 Set과 같은 자료구조를 이용해서 positive number 의 유무를 판별할 수 없다는 뜻이다.

문제에서 Missing Positive Number를 찾으라고 했으므로, 음수는 우리의 관심사밖이다. 그래서 해당 인덱스의 부호를 음으로 바꿔주는 것으로, 추가적인 space의 할당없이 숫자의 존재여부를 저장할 수 있다.

class Solution
{
public:
    int firstMissingPositive(vector<int> &nums)
    {
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            if (nums[i] <= 0 || nums[i] > n)
            {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; i++)
        {
            int absNum = abs(nums[i]);
            if (absNum > n)
                continue;
            nums[absNum - 1] = -abs(nums[absNum - 1]);
        }
        for (int i = 0; i < n; i++)
        {
            if (nums[i] > 0)
            {
                return i + 1;
            }
        }
        return n + 1;
    }
};