Python 에서 배열 부분 최대 값 의 인 스 턴 스 를 구 합 니 다.

배열 부분 최대 값 구하 기
중복 요소 가 없 는 배열 A[0...N-1]을 지정 하여 이 배열 의 부분 최대 치 를 찾 으 십시오.규정:배열 경계 밖의 값 은 무한 하고 작다.즉:A[0]>A[-1],A[N-1]>A[N].
분명히 한 번 훑 어보 면 전역 최대 치 를 찾 을 수 있 지만 전역 최대 치 는 국부 최대 치 이다.
더 빠 른 방법 이 있 을까요?
알고리즘 설명
색인 left,right 를 사용 하여 각각 배열 의 끝 을 가리킨다.
중간 점 mid=(left+right)/2
A[mid]>A[mid+1],후반 부 버 리 기:right=mid
A[mid+1]>A[mid],전반 기 버 리 기:left=mid+1
left==right 까지 재 귀적
시간 복잡 도 는 O(logN)이다.
파 이 썬 코드

def local_maximum(li):
  if li is None:
    return
  left = 0
  right = len(li) - 1
  while left < right:
    mid = int((left + right) / 2)
    if li[mid] > li[mid + 1]:
      right = mid
    else:
      left = mid + 1
  return li[left]


if __name__ == '__main__':
  li = [1, 5, 2, 3, 4, 0]
  result = local_maximum(li)
  print(result)
출력 결과:4
이상 의 Python 에서 배열 부분 에서 가장 큰 값 을 구 하 는 인 스 턴 스 는 바로 편집장 이 여러분 에 게 공유 한 모든 내용 입 니 다.여러분 께 참고 가 되 고 저 희 를 많이 사랑 해 주 셨 으 면 좋 겠 습 니 다.

좋은 웹페이지 즐겨찾기