首页 > 代码库 > Find Peak Element --leetcode
Find Peak Element --leetcode
原题链接:https://oj.leetcode.com/problems/find-peak-element/
题目大意:给定一个相邻元素不相等的数组,找出其中的一个局部最大值,返回对应下标。
方法1:顺序遍历。
本题的一个重要特点是,从第一个元素开始,若其大于相邻的后续元素,则第一个元素就是一个局部最大值,返回即可。若其小于相邻的后续元素,则第二个元素大于第一个元素。如此,一一遍历数组,第一次出现,第i个元素若大于其相邻后续元素,则该元素就是一个局部最大值,返回即可。代码如下:
class Solution { public: int findPeakElement(const vector<int> &num) { for(int i=1;i<num.size();i++){ if(num[i]<num[i-1]) return i-1; } return num.size()-1; } };
时间复杂度:最坏O(N)
方法2:二分查找
思路:如果中间元素大于其相邻后续元素,则中间元素左侧(包含该中间元素)必包含一个局部最大值。如果中间元素小于其相邻后续元素,则中间元素右侧必包含一个局部最大值。
class Solution { public: int findPeakElement(const vector<int> &num) { int left=0,right=num.size()-1; while(left<=right){ if(left==right) return left; int mid=(left+right)/2; if(num[mid]<num[mid+1]) left=mid+1; else right=mid; } } };时间复杂度:O(lgN)
题目不错,是binary search的延续,可以和二分查找相关的算法一起做个总结。
Find Peak Element --leetcode
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。