首页 > 代码库 > [LintCode] Find Peak Element 求数组的峰值
[LintCode] Find Peak Element 求数组的峰值
There is an integer array which has the following features:
- The numbers in adjacent positions are different.
- A[0] < A[1] && A[A.length - 2] > A[A.length - 1].
We define a position P is a peek if:
A[P] > A[P-1] && A[P] > A[P+1]Find a peak element in this array. Return the index of the peak.
Notice
The array may contains multiple peeks, find any of them.
Have you met this question in a real interview?
Example
Given [1, 2, 1, 3, 4, 5, 7, 6]
Return index 1 (which is number 2) or 6 (which is number 7)
Challenge
Time complexity O(logN)
LeetCode上的原题，请参见我之前的博客Find Peak Element。
解法一：
class Solution {public: /** * @param A: An integers array. * @return: return any of peek positions. */ int findPeak(vector<int> A) { int left = 0, right = A.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (A[mid] < A[mid + 1]) left = mid + 1; else right = mid; } return right; }};
解法二：
class Solution {public: /** * @param A: An integers array. * @return: return any of peek positions. */ int findPeak(vector<int> A) { for (int i = 1; i < A.size(); ++i) { if (A[i] < A[i - 1]) return i - 1; } return A.size() - 1; }};
[LintCode] Find Peak Element 求数组的峰值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。