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)の時間的複雑度および定数空間的複雑度で行うことが要求される.
1つの方法は、まず配列内の正の整数をi位からi-1位に置くことで、秩序あるシーケンスが形成され、次に各下付きindex現在の要素値をチェックすることで、現在の下付きに対応する正の整数が欠落しているかどうかを知ることができ、欠落している場合は下付きindex + 1に戻ることである.
三.サンプルコード

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int firstMissingPositive(vector<int>& 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;
    }
};