LeetCode 40. First Missing Positive

818 ワード

O(n)時間,定数空間で問題を解くことが要求される.だから早く並ぶことはできません.
なお、A[i]>0&&A[i]<=nの数については、配列の中で最終的にA[i]==i+1を満たすと、最後に配列を遍歴し、A[i]==i+1を満たさない最初の数を見つけ、i+1を返すだけでよい.
したがって配列を遍歴し,毎回iと表記される反復において,A[i]>0&&A[i]<=n&&A[i]!=i+1 && A[i]!=A[A[i]-1]は、絶えずswap(A[i],A[A[i]-1]);
拘束条件A[i]!=A[A[i]−1]は入力が[1,1]の場合を扱うためであり,この条件がなければi=1に反復するとデッドサイクルに陥る.
コード:
class Solution 
{
public:
    int firstMissingPositive(int A[], int n) 
    {
    	for (int i = 0; i < n; ++ i)
    	{
    		while (A[i]>0 && A[i]<=n && A[i]-1!=i && A[A[i]-1]!=A[i])
    		{
    			swap(A[i], A[A[i]-1]);
    		}
    	}
    	for (int i = 0; i < n; ++ i)
    	{
    		if (A[i]-1 != i )
    		{
    			return i + 1;
    		}
    	}

    	return n+1; 
    }
};