leetcode筆記：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.

二. 題目分析

該題的大意是給定一個未排序的數組，該數組可能包含零或正負數，要求找出第一個未出現的正數。例如[1, 2, 0]，由於第一個未出現的正整數是3，則返回3；[3, 4, -1, 1]第一個未出現的正整數是2，則返回2。算法要求在O(n)的時間復雜度及常數空間復雜度內完成。

一種方法是，先把數組裡每個正整數從i位放到第i-1位上，這樣就形成了有序的序列，然後檢查每一下標index與當前元素值，就能知道當前下標所對應的正整數是否缺失，若缺失則返回下標index + 1即可。

三. 示例代碼

#include 
#include 

using namespace std;

class Solution
{
public:
    int firstMissingPositive(vector& nums)
    {
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            int temp = 0;
            while (i + 1 != nums[i] && nums[i] != nums[nums[i] - 1] && nums[i] > 0)
            {
                temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

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

        return n + 1;
    }
};