leetcode 검 지 Offer 11. 회전 배열 의 최소 숫자

검 은 Offer 11. 회전 배열 의 최소 숫자 를 말 합 니 다. 한 배열 의 처음에 몇 개의 요 소 를 배열 의 끝 에 옮 기 는 것 을 우 리 는 배열 의 회전 이 라 고 부 릅 니 다.정렬 이 증가 하 는 배열 의 회전 을 입력 하고 회전 배열 의 최소 요 소 를 출력 합 니 다.예 를 들 어 배열 [3, 4, 5, 1, 2] 은 [1, 2, 3, 4, 5] 의 회전 이 고 이 배열 의 최소 치 는 1 이다.
예시 1:
입력: [3, 4, 5, 1, 2] 출력: 1 예시 2:
입력: [2, 2, 2, 0, 1] 출력: 0
이 문 제 는 주로 이분법 을 고찰 하려 고 하 는데, 이곳 의 이분법 은 이전의 것 과 또 약간 다르다.아래 의 분석 을 통 해 힘 이 큰 사람의 해석 을 막는다.
순환 2 분: 설정 i, j 지침 은 각각 numbers 배열 좌우 양쪽 을 가리 키 며 m = (i + j) / / 2 는 매번 2 분 의 중심 점 ("/ /" 은 아래로 나 누 는 방법 을 대표 하기 때문에 i ≤ m 가 항상 있 습 니 다.

numbers [m] > numbers [j] 시 m 는 반드시 왼쪽 정렬 배열 에 있 습 니 다. 즉, 회전 점 x 는 반드시 [m + 1, j] 닫 힌 구간 에 있 기 때문에 i = m + 1 을 실행 합 니 다.

numbers [m] < numbers [j] 시: m 는 반드시 오른쪽 정렬 배열 에 있 습 니 다. 즉, 회전 점 x 는 반드시 [i, m] 닫 힌 구간 에 있 기 때문에 j = m 를 실행 합 니 다.

numbers [m] = = numbers [j] 시 m 가 어느 정렬 배열 에 있 는 지 판단 할 수 없습니다. 즉, 회전 점 x 가 [i, m] 인지 [m + 1, j] 구간 에 있 는 지 판단 할 수 없습니다. 해결 방안: j = j - 1 을 실행 하여 판단 범 위 를 축소 합 니 다 (분석 은 다음 과 같 습 니 다).

주의: mm 가 왼쪽 (오른쪽) 에서 배열 을 정렬 할 수 없습니다. 다음 두 개의 회전 점 값 이 00 인 예제 배열 을 설정 하면 i = 0 i = 0, j = 4j = 4 시 m = 2m = 2 로 두 예제 결과 가 다 릅 니 다.
예 [1, 0, 1, 1, 1]: 회전 점 x = 1, 따라서 m = 2 는 오른쪽 정렬 배열 에 있 습 니 다. 예 [1, 1, 1, 0, 1]: 회전 점 x = 3, 따라서 m = 2 는 왼쪽 정렬 배열 에 있 습 니 다.
여기 서 right 를 1 로 줄 이 는 것 은 경 계 를 줄 이 는 것 과 같 습 니 다. 매번 한 자 리 를 줄 이 고 오른쪽 에 있 는 중복 숫자 를 제외 할 때 까지 합 니 다.
작성 자: jyd 링크:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/ 출처: 리 트 코드 (LeetCode) 저작권 은 작가 에 게 있 습 니 다. 상업 전 재 는 작가 에 게 연락 하여 권한 을 수 여 받 으 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        if not numbers: return 
        left, right = 0 , len(numbers)-1
        while left < right:#    ,      ， > ， 
            mid = (left + right) // 2
            # print(left, mid,right)
            if numbers[mid] > numbers[right]:
                left = mid + 1
            elif numbers[mid] < numbers[right]:
                right = mid
            else:#                  
                right -= 1
        return numbers[left]