首页 > 代码库 > 九章算法--寻找数组波峰
九章算法--寻找数组波峰
题目描述：一 个数组A[1..n]，假设数组中没有任何相邻两数相等，满足A[1]<A[2]，A[n-1]>A[n]。A[i]被称为波峰，当且仅当 A[i]>A[i-1]并且A[i]>A[i+1]。请找到数组中的一个波峰。假设数组中存在相邻相等的数，该怎么做？
二分法寻找一个波峰，
如果数组存在相邻相等的元素则必须O（n）
1 /************************************************************************* 2 > File Name: ArrayWaveCrest.cpp 3 > Author: zhoukang1991 4 > Mail: zhoukang199191@126.com 5 > Created Time: 2014年08月29日 星期五 21时36分24秒 6 ************************************************************************/ 7 8 #include <iostream> 9 #include <vector>10 #include <climits>11 using namespace std;12 13 int findcrest(const vector<int> &arr){14 int left = 0;15 int right = arr.size()-1;16 int n = arr.size();17 while(left <= right){18 int mid = left + (right-left)>>1;19 if(mid == 0){20 left = 1;21 continue;22 }23 if(mid == n-1){24 right = n-2;25 continue;26 }27 28 if( arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]){29 return arr[mid];30 }31 else if(arr[mid] < arr[mid-1]){32 right = mid-1;33 }34 else{35 left = mid+1;36 }37 }38 return INT_MIN;39 }40 41 int main(){42 vector<int> v;43 v.push_back(1);44 v.push_back(2);45 v.push_back(3);46 v.push_back(2);47 v.push_back(1);48 cout<<findcrest(v)<<endl;49 return 0;50 }
九章算法--寻找数组波峰
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。