162. Find Peak Value Leetcode Python
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
click to show spoilers.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
この問題はMIT open course wareの最初の授業で話した例題で、解法はたくさんありますが、一番いいのは二分法のクエリーです.
考慮する境界条件は
1.elementが1つしかない場合
2.シーケンス全体がIncreasingとdecreasingのみの場合
コードは次のとおりです.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
click to show spoilers.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
この問題はMIT open course wareの最初の授業で話した例題で、解法はたくさんありますが、一番いいのは二分法のクエリーです.
考慮する境界条件は
1.elementが1つしかない場合
2.シーケンス全体がIncreasingとdecreasingのみの場合
コードは次のとおりです.
class Solution:
# @param num, a list of integer
# @return an integer
def findPeakElement(self, num):
low=0
high=len(num)-1
if high==low:
return 0
while low<high:
mid=low+(high-low)/2
if num[mid]>num[mid+1] and num[mid]>num[mid-1]:
return mid
if num[mid]>num[mid+1]:
high=mid-1
elif num[mid]<=num[mid+1]:
low=mid+1
return low