검지 offer - python - 06 - 회전 배열 의 최소 숫자
2311 단어 검지 offer - python
한 배열 의 맨 처음 몇 개의 요 소 를 배열 의 끝 에 옮 기 는 것 을 우 리 는 배열 의 회전 이 라 고 부른다.정렬 되 지 않 은 배열 의 회전 을 입력 하고 회전 배열 의 최소 요 소 를 출력 합 니 다.예 를 들 어 배열 {3, 4, 5, 1, 2} 은 {1, 2, 3, 4, 5} 의 회전 이 고 이 배열 의 최소 값 은 1 이다.NOTE: 제 시 된 모든 요 소 는 0 보다 큽 니 다. 배열 크기 가 0 이면 0 을 되 돌려 주 십시오.
프로그램 설계 에 자주 사용 되 는 알고리즘 찾기 와 정렬:
정렬 된 배열 (또는 일부 정렬 된 배열) 에서 숫자 를 찾 거나 숫자 가 나타 나 는 횟수 를 집계 하 라 고 요구 하면 이분법 으로 찾 아 볼 수 있 습 니 다.
이분법 파 이 썬 찾기
해시 표 와 이 진 트 리 에서 찾 는 중점 은 알고리즘 이 아 닌 데이터 구 조 를 고찰 하 는 데 있다.해시 표 의 장점 은 O (1) 시간 에 특정한 요 소 를 찾 을 수 있 고 효율 적 인 검색 방식 이다.그러나 단점 은 해시 표를 실현 하기 위해 서 는 별도의 공간 이 필요 하 다 는 것 이다.
이 진 트 리 검색 알고리즘 에 대응 하 는 데이터 구 조 는 이 진 트 리 입 니 다.
찾기 보다 정렬 이 복잡 하 다.정렬, 거품 정렬, 병합 정렬, 빠 른 정렬 등 서로 다른 알고리즘 을 삽입 하 는 것 이 빠 릅 니 다 (공간 소모, 평균 시간 복잡 도, 최 악의 시간 복잡 도). 특히 손 으로 훑 는 빠 른 정렬 은 자주 고찰 됩 니 다.각종 정렬 알고리즘 Python 이 이동 을 실현 합 니 다.
가장 직관 적 인 방법 은 처음부터 끝까지 배열 을 한 번 옮 겨 다 니 며 최소 치 를 찾 는 것 이다. 시간 복잡 도 는 O (n) 이지 만 회전 배열 의 특징 을 이용 하지 않 았 다.
회전 한 후의 배열 은 두 개의 정렬 된 하위 배열 로 나 눌 수 있 고 앞의 하위 배열 요 소 는 모두 후 면 배열 요소 보다 크 거나 같 음 을 알 수 있다.또한 가장 작은 요소 가 바로 이 두 개의 배열 의 경계선 이라는 것 을 알 수 있다.정렬 배열 에서 2 분 검색 법 으로 O (logn) 의 검색 을 실현 할 수 있 습 니 다.
이 문제 에서 제시 한 배열 은 어느 정도 정렬 되 어 있 기 때문에 이분 검색 법의 사고 로 이 최소 요 소 를 찾 아 볼 수 있다.
1) 우 리 는 두 바늘 로 배열 의 첫 번 째 요소 와 마지막 요 소 를 가리킨다.제목 에서 회전 규칙 에 따라 첫 번 째 요 소 는 마지막 요소 보다 크 거나 같 아야 합 니 다.
2) 중간 원소 찾기
검색 범 위 를 매번 반 으로 축소 합 니 다.마지막 으로 첫 번 째 지침 은 앞 면 배열 의 마지막 요 소 를 가리 키 고 두 번 째 지침 은 뒤 면 배열 의 첫 번 째 요 소 를 가리킨다.즉, 그들 은 최종 적 으로 두 개의 인접 요 소 를 가리 키 고 두 번 째 지침 이 가리 키 는 것 은 바로 가장 작은 요소 이다.
특수 한 경우, 배열 에 대량의 중복 요소 가 있 을 때, 예 를 들 어 {1, 0, 1, 1, 1} 은 2 분 검색 으로 1 을 되 돌려 주기 때문에 순서대로 만 찾 을 수 있 습 니 다.
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
low = 0
high = len(rotateArray) -1
while low < high:
mid = (low + high) // 2
if rotateArray[mid] > rotateArray[high]:
low = mid + 1
else:
high = mid
return rotateArray[low]좋은 웹페이지 즐겨찾기
