면접: 배열: 첫 번 째 정수

2123 단어
제목.
무질서 한 정형 배열 을 정 하고 첫 번 째 배열 에 없 는 정 수 를 찾 아 라.요구 시간 복잡 도 는 O (n) 이 고 공간 복잡 도 는 O (1) 이다.
  • 예 를 들 어 배열 {5, 3, - 1, 1} 을 입력 하여 2
    • 로 되 돌려 줍 니 다.
    알고리즘
  • 하 쉬 사상 을 빌리다
  • 배열 의 작은 표 지 는 해당 하 는 값 을 저장 합 니 다. A [K - 1] = K
  • 배열 의 길이 보다 크 고 1 보다 작은 숫자 에 대해 포기 합 니 다.
  • 새로운 배열 이 생기 면 처음부터 첫 번 째 A [k - 1] 가 k 와 같 지 않 은 것 을 만나면 k
    • 를 출력 한다.
  • 배열 길이 만 있 는 다음 정수 {1, 2, 3, 4} 을 만 나 지 않 았 다 면;돌아 가기 5 
    • import java.util.*;

class Solution{
    public int firstMissingPositive(int[] A){
        int n=A.length;
        for(int i=0;i<n;++i){
            if(A[i]>0 && A[i]<=n){
                if(A[i]-1 !=i && A[A[i]-1]!=A[i]){
                    //       
                    int temp=A[A[i]-1];
                    A[A[i]-1]=A[i];
                    A[i]=temp;
                    //          A[i]     
                    i--;
                }
            }
        }
        for(int i=0;i<n;++i)
            //           
            if(A[i]-1 !=i)
                return i+1;
        //    
        return n+1;
    }
}
    ACM--string 일반적인 사용 방법
    AngularJS의 의존 주입

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage