首页 > 代码库 > leetcode 【 Find Peak Element 】python 实现
leetcode 【 Find Peak Element 】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.
代码：
分别用递归和非递归两种方法实现。
非递归版代码：oj测试通过 Runtime: 55 ms
1 class Solution: 2 # @param num, a list of integer 3 # @return an integer 4 def findPeakElement(self, num): 5 if len(num) == 1 : 6 return 0 7 if len(num) == 2 : 8 return [0,1][num[0] < num[1]] 9 start = 010 end = len(num)-111 while start <= end:12 if start == end:13 return start14 if start+1 == end:15 return [start,end][num[start] < num[end]]16 mid = (start+end)/217 if num[mid] < num[mid-1]:18 #start = 019 end = mid -120 elif num[mid] < num[mid+1]:21 start = mid+122 #end = len(num)-123 else:24 return mid
递归代码：oj测试通过 Runtime: 51 ms
1 class Solution: 2 # @param num, a list of integer 3 # @return an integer 4 def find(self,num,start,end): 5 if start == end : 6 return start 7 if end == start + 1: 8 if num[start] < num[end] : 9 return end10 else:11 return start12 mid = (start+end)/213 if num[mid] < num[mid-1] :14 return self.find(num, start, mid-1)15 if num[mid] < num[mid+1] :16 return self.find(num, mid, end)17 return mid18 19 def findPeakElement(self, num):20 if len(num) == 1:21 return 022 return self.find(num, 0, len(num)-1)
思路：
二分查找思路升级版。参照如下两篇日志的思路：
http://bookshadow.com/weblog/2014/12/06/leetcode-find-peak-element/
http://blog.csdn.net/u010367506/article/details/41943309
这道题在理解题意上需要注意就是默认这个数组的虚头和虚尾都是负无穷，并且这个数组不存在相等的两个元素，这样就一定能够找到题中描述的peak point.
leetcode 【 Find Peak Element 】python 实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。