189.First Missing Positive-잃 어 버 린 첫 번 째 정수(중간 문제)

잃 어 버 린 첫 번 째 정수
4.567917.문 제 는 무질서 한 정수 조 를 제시 하여 그 중에서 나타 나 지 않 은 최소 정 수 를 찾 아 라
4.567917.사례 를 제시 하면[1,2,0],return 3 을 제시 하면[3,4,-1,1],return 24.567917.도전 은 시간 복잡 도 O(n)의 알고리즘 만 허용 하고 상수 등급 의 공간 만 사용 할 수 있 습 니 다
4.567917.문 제 는 통 정렬 원 리 를 사용 하여 A[i](0 이상 이 고 A 와 같은 길이 보다 작 음)를 교환 을 통 해 A[A[i]-1]에 놓 고 마지막 으로 첫 번 째 부족 한 수 를 다시 한 번 반복 해서 찾 습 니 다.예 를 들 어[3,4,-1,1]교환 을 통 해[-1,4,3,1][-1,1,3,4]를 얻 고 첫 번 째 부족 한 수 는 2 이다.A[i]교환의 제한 조건 은:1.A[i]>0 2.A[i]<=A[i].length 3.A[i]!=A[A[i]-1]사순환 피하 기

public class Solution {
    /**    
     * @param A: an array of integers
     * @return: an integer
     */
    public int firstMissingPositive(int[] A) {
        for (int i = 0; i < A.length; i++) 
        {
            while (A[i] <= A.length && A[i] > 0 && A[A[i] - 1] != A[i]) 
            {
                swap(A, i, A[i] - 1);    
            }
        }

        for (int i = 0; i < A.length; i++) 
        {
            if (A[i] != i + 1) 
            {
                return i + 1;
            }
        }

        return A.length + 1;
    }

    public void swap(int[] A, int l, int r) 
    {
        int tmp = A[l];
        A[l] = A[r];
        A[r] = tmp;
    }
}

Last Update 2016.10.28