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.解题思路:
用Binary Search
Python 解法:
class Solution: # @param num, a list of integer # @return an integer def findPeakElement(self, num): def findPeakElementByBinarySearch(num, i, j): mid = (i + j)/2 if mid < j and num[mid + 1] > num[mid]: return findPeakElementByBinarySearch(num, mid + 1, j) if mid > i and num[mid - 1] > num[mid]: return findPeakElementByBinarySearch(num, i, mid - 1) return num[mid] return self.findPeakElementByBinarySearch
No comments:
Post a Comment