[댓 글] 회전 배열 의 최소 요소

다음으로 이동:http://zhedahht.blog.163.com/blog/static/25411174200952765120546/
    제목: 한 배열 의 처음에 몇 개의 요 소 를 배열 의 끝 에 옮 겨 서 우 리 는 배열 의 회전 이 라 고 부른다.정렬 된 배열 의 회전 을 입력 하고 회전 배열 의 최소 요 소 를 출력 합 니 다.예 를 들 어 배열 {3, 4, 5, 1, 2} 은 {1, 2, 3, 4, 5} 의 회전 이 고 이 배열 의 최소 값 은 1 이다.
    분석: 이 문제 의 가장 직관 적 인 해법 은 어렵 지 않다.처음부터 끝까지 배열 을 한 번 훑 어보 면 가장 작은 요 소 를 찾 을 수 있 고 시간 복잡 도 는 분명히 O (N) 이다.그러나 이 사 고 는 입력 배열 의 특성 을 이용 하지 않 았 기 때문에 우 리 는 더 좋 은 해법 을 찾 을 수 있 을 것 이다.
    우 리 는 회전 한 후의 배열 이 실제 적 으로 두 개의 정렬 된 하위 배열 로 나 눌 수 있 고 앞의 하위 배열 의 요 소 는 모두 뒷 면 배열 의 요소 보다 크 거나 같다 는 것 을 알 게 되 었 다.우 리 는 또한 가장 작은 원소 가 바로 이 두 개의 하위 그룹의 경계선 이라는 것 을 알 수 있다.우 리 는 이원 검색 법의 사고방식 으로 이 가장 작은 원 소 를 찾 으 려 고 한다. 먼저 우 리 는 두 개의 바늘 로 수조 의 첫 번 째 원소 와 마지막 원 소 를 가리 키 고 제목 에 따라 회전 하 는 규칙 에 따라 첫 번 째 원 소 는 마지막 원소 보다 크 거나 같 아야 한다 (이것 은 사실 완전히 맞지 않 고 특례 도 있다. 그 다음 에 특례 를 토론 해 야 한다).이 어 우 리 는 배열 중간 에 있 는 요 소 를 얻 었 다. 만약 에 이 중간 요소 가 앞의 증가 서브 배열 에 있다 면 첫 번 째 포인터 가 가리 키 는 요소 보다 크 거나 같 아야 한다. 이때 배열 에서 가장 작은 요 소 는 이 중간 요소 의 뒤에 있어 야 한다. 우 리 는 첫 번 째 포인터 가 이 중간 요 소 를 가리 키 면 찾 는 범 위 를 좁 힐 수 있다.만약 에 중간 요소 가 뒤의 증가 서브 배열 에 있다 면 두 번 째 포인터 가 가리 키 는 요소 보다 작 거나 같 아야 한다. 이때 이 배열 에서 가장 작은 요 소 는 이 중간 요소 의 앞 에 있어 야 한다. 우 리 는 두 번 째 지침 을 이 중간 요 소 를 가리 키 면 똑 같이 찾 는 범 위 를 좁 힐 수 있다.우 리 는 이어서 업 데 이 트 된 두 개의 지침 으로 새로운 중간 요 소 를 얻 고 비교 하 며 순환 했다.
    상기 사고 에 따 르 면 우리 의 첫 번 째 지침 은 항상 앞 에 배열 의 요 소 를 증가 시 키 는 것 을 가리 키 고 두 번 째 지침 은 항상 뒤에 배열 의 요 소 를 증가 시 키 는 것 을 가리킨다. 마지막 으로 첫 번 째 지침 은 앞 에 배열 의 마지막 요 소 를 가리 키 고 두 번 째 지침 은 뒤의 체면 배열 의 첫 번 째 요 소 를 가리킨다. 즉, 그들 은 최종 적 으로 두 개의 인접 한 요 소 를 가리킨다.두 번 째 바늘 이 가리 키 는 것 은 가장 작은 원소 다.이것 이 바로 순환 이 끝 나 는 조건 이다.이 사고방식 을 바탕 으로 우 리 는 다음 과 같은 코드 를 쓸 수 있다.

// Get the minimum number of a roatation of a sorted array
int Min(int *numbers, int length)
{
    if(numbers == 0 || length <= 0)
        throw new std::exception("Invalid parameters");

    int index1 = 0;
    int index2 = length - 1;
    int indexMid = index1;

    while(numbers[index1] >= numbers[index2]) 
    {
        if(index2 - index1 == 1) {
            indexMid = index2;
            break;
        }

        indexMid = (index1 + index2) / 2;
        if(numbers[indexMid] >= numbers[index1])
            index1 = indexMid;
        else if(numbers[indexMid] <= numbers[index2])
            index2 = indexMid;
    }

    return numbers[indexMid];
}

    우리 가 매번 찾 는 범 위 를 반 으로 줄 이기 때문에 이 알고리즘 의 시간 복잡 도 는 O (logN) 이다.주의해 야 할 것 은 면접 현장에서 코드 를 쓰 면 보통 테스트 사례 로 코드 가 정확 한 지 검증 해 야 한 다 는 점 이다. 우 리 는 검증 할 때 최대한 전면적 인 것 을 고려 해 야 한다.이 문제 와 같이 우 리 는 가장 간단 한 테스트 용례 를 내 는 것 외 에 적어도 다음 과 같은 상황 을 고려 해 야 한다.
    (1) 배열 앞의 0 개의 요 소 를 맨 앞에서 맨 뒤로 옮 기 는 것 이다. 즉, 원래 배열 은 변경 하지 않 고 제목 의 규칙 에 따라 이것 도 회전 이다. 이때 배열 의 첫 번 째 요 소 는 마지막 요소 보다 작 거나 같다.
    (2) 정렬 된 배열 에 똑 같은 요소 가 있 을 수 있 으 므 로 우 리 는 특히 두 가지 상황 에 주의해 야 한다.하 나 는 회전 한 후의 배열 에서 첫 번 째 요소 와 마지막 요 소 는 같다.다른 상황 은 가장 작은 요소 가 배열 에서 반복 되 는 것 이다.
    (3) 앞의 코드 에서 입력 한 배열 이 정렬 배열 의 회전 이 아니라면 순환 에 빠 질 수 있 으 므 로 면접 관 과 배열 의 유효성 을 판단 해 야 하 는 지 논의 해 야 한다.면접 을 볼 때 면접 관 은 입력 의 유효성 을 어떻게 검증 하 는 지 에 대해 토론 하면 우리 의 사고방식 의 엄밀 성 을 나 타 낼 수 있다.본 고 는 함수 Min 을 호출 하기 전에 입력 의 유효성 을 검증 했다 고 가정 한다.
    (4) 마지막 으로 지적 해 야 할 것 은 입력 한 배열 지침 이 불법 지침 이 라면 우 리 는 이상 으로 오 류 를 처리 하 는 것 이다.이 는 이러한 상황 에서 우리 가 return 으로 이 함 수 를 끝내 면 모든 숫자 를 되 돌려 주 는 것 이 정확 하지 않 기 때문이다.