Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 피크 요소 찾기

<시간/>

배열에서 피크 요소를 찾아야 한다고 가정합니다. 피크 요소는 이웃보다 큰 요소입니다. nums[i] ≠ nums[i+1]인 입력 배열 nums가 있다고 가정하고 피크 요소를 검색하고 해당 인덱스를 반환합니다. 배열은 여러 피크 요소를 보유할 수 있으며, 이 경우 피크 요소 중 하나에 대한 인덱스를 반환합니다. nums[-1] =nums[n] =-∞라고 상상할 수 있습니다. 따라서 배열이 [1,2,1,3,5,6,4]와 같으면 피크 요소는 1 또는 5여야 ​​합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • low :=0 및 high :=배열의 마지막 인덱스, n :=배열의 크기, ans :=무한대
  • 낮은 동안 <=높음
    • 중간 :=낮음 + (높음 - 낮음)/2
    • mid – 1>=0이고 nums[mid – 1] <=nums[mid]이면 low :=mid, 그렇지 않으면 high :=mid - 1
  • 낮은 수익

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution(object):
   def findPeakElement(self, nums):
      low = 0
      high = len(nums)-1
      while low<high:
         mid = low + (high - low+1)//2
         if (mid-1>=0 and nums[mid-1]<=nums[mid]):
            low = mid
         else:
            high = mid-1
      return nums[low+1]
ob1 = Solution()
print(ob1.findPeakElement([15,35,85,96,5,6,8,12]))

입력

[15,35,85,96,5,6,8,12]

출력

5