프로그래머 면접 금전 - 5.6 빠 진 부분 찾기

제목 설명
배열 A 는 0 에서 n 까지 의 모든 정 수 를 포함 하지만 그 중 하 나 를 잃 었 다.이 문제 에 대해 우 리 는 제한 을 설정 하여 한 번 의 조작 으로 배열 number 의 전체 내용 을 얻 을 수 없 게 합 니 다.유일한 사용 가능 한 동작 은 배열 에서 i 번 째 요소 의 바 이 너 리 j 위 (최저 위 는 0 위) 를 묻 는 것 입 니 다. 이 작업 의 시간 복잡 도 는 상수 입 니 다. 알고리즘 을 설계 하여 O (n) 시간 내 에 이 수 를 찾 으 십시오.
하나의 배열 number, 즉 모든 나머지 수 를 작은 것 에서 큰 것 으로 배열 하 는 바 이 너 리 여러분 의 값 을 지정 합 니 다. 예 를 들 어 A [0] [1] 은 나머지 두 번 째 수 바 이 너 리 가 낮은 것 에서 높 은 것 으로 두 번 째 를 표시 합 니 다.동시에 int n 을 정 합 니 다. 의 미 는 문제 와 같 습 니 다.부족 한 수 를 되 돌려 주세요.
테스트 샘플:

[[0],[0,1]]

  ：1

2. 제목 사고
제목 의 대 의 는 배열 A 에 0 에서 n 까지 의 정수 (하나 가 적 음) 가 포함 되 어 있 고 부족 한 이 정 수 를 찾 는 것 이다.배열 에 저 장 된 것 은 이 양수 의 바 이 너 리 이기 때문에 매번 방문 할 때마다 이 수의 한 자리 에 만 접근 할 수 있 습 니 다. 알고리즘 복잡 도 비트 O (N).
배열 은 순서대로 배열 되 어 있 기 때문에 배열 중의 i 번 째 정수 0 위 는 반드시 0, 1 순서에 따라 교체 하여 바 뀌 어야 한다. 만약 에 두 개의 연속 적 인 1 또는 0 이 나타 나 면 문제 가 생 겼 다 는 것 을 의미한다.구체 적 인 조작 은
0 - n 차례로 옮 겨 다 니 며 사용 할 수 있 습 니 다.
2 분 동안 찾 는 방법 으로 목표 치 를 찾 습 니 다.
코드
1. 0 부터 n 까지 차례로 옮 겨 다 니 는 방식

if(numbers==null || n<0)
            return -1;
        int count=0;
        for(int i=0;i

2. 이분 검색 방식

if(numbers==null || n<0)
            return -1;
        int left=0;
        int right=numbers.length-1;
        while(left<=right){
            int middle=left+(right-left)/2;
            if(numbers[middle][0]==(middle&1))
                left=middle+1;
            else{
                right=middle-1;
                flag=true;
            }
               	
        }
        if(left==numbers.length)//        ，   n-1         ，         n
            return n;
        return left;

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

LRU 캐 시 메커니즘 (LeetCode 146 번) 자바 구현

LRU (최근 최소 사용) 캐 시 메커니즘.다음 동작 을 지원 해 야 합 니 다: 데이터 가 져 오기 get 기록 데이터 put 。 데이터 가 져 오기 get(key) - 키 (key) 가 캐 시 에 존재...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

프로그래머 면접 금전 - 5.6 빠 진 부분 찾기

좋은 웹페이지 즐겨찾기