【題目】
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.
click to show spoilers.
Note:
Your solution should be in logarithmic complexity.
【分析一】
我們首先想到的就是時間復雜度為O(n)的順序遍歷，對每一個元素，與它相鄰的元素比較。
這樣也可以AC。
Your solution should be in logarithmic complexity.
可是題目要求是時間復雜度是對數級別的。
【代碼一】
/*********************************
* 日期：2015-01-31
* 作者：SJF0115
* 題目: 162.Find Peak Element
* 網址：www.2cto.com
* 結果：AC
* 來源：LeetCode
* 博客：
**********************************/
#include
#include
#include
using namespace std;
class Solution {
public:
int findPeakElement(const vector &num) {
int size = num.size();
if(size == 1){
return 0;
}//if
// 判斷第一個元素和最後一個元素
if(size > 1){
if(num[0] > num[1]){
return 0;
}//if
if(num[size-1] > num[size-2]){
return size-1;
}//if
}//if
for(int i = 1;i < size-1;++i){
if(num[i] > num[i-1] && num[i] > num[i+1]){
return i;
}//if
}//for
}
};
int main(){
Solution solution;
// vector num = {1,2,3,1};
//vector num = {4,3,3,1};
vector num = {1,2,3,4};
int result = solution.findPeakElement(num);
// 輸出
cout<
【分析二】
根據給出的條件： num[i] != num[i+1], 相鄰兩個元素不相等。運用二分查找原理。
（1）如果 num[i-1] < num[i] > num[i+1], 則num[i] 就是 peak
（2）如果 num[i-1] < num[i] < num[i+1], 則 num[i+1...n-1] 必定包含一個 peak
（3）如果 num[i-1] > num[i] > num[i+1], 則num[0...i-1]
必定包含一個 peak
（4）如果 num[i-1] > num[i] < num[i+1], 則 兩邊都有一個 peak
繼續優化一下，通過上面仔細觀察一下：
（1）如果 num[i-1] < num[i] > num[i+1], 則num[i] 就是 peak
（2）如果 num[i-1] < num[i] , 則 num[i+1...n-1] 必定包含一個 peak，left指向mid+1
（3）如果 num[i-1] > num[i] , 則num[0...i-1] 必定包含一個 peak,right指向mid-1
【代碼二】
/*------------------------------------
* 日期：2015-01-31
* 作者：SJF0115
* 題目: 162.Find Peak Element
* 網址：https://oj.leetcode.com/problems/find-peak-element/
* 結果：AC
* 來源：LeetCode
* 博客：
---------------------------------------*/
#include
#include
#include
using namespace std;
class Solution {
public:
int findPeakElement(const vector &num) {
int size = num.size();
// only one element
if (size == 1) {
return 0;
}//if
int left = 0, right = size - 1;
int mid;
// left right 距離為1 退出
while (left < right - 1) {
mid = left + (right - left) / 2;
// If num[i-1] < num[i] > num[i+1],then num[i] is peak
if (num[mid] > num[mid - 1] && num[mid] > num[mid + 1]) {
return mid;
}//if
// If num[i-1] < num[i],then num[i+1...n-1] must contains a peak
if (num[mid - 1] < num[mid]) {
left = mid + 1;
}//if
// If num[i-1] > num[i], then num[0...i-1] must contains a peak
else {
right = mid - 1;
}//else
}//while
return num[left] > num[right] ? left : right;
}
};
int main(){
Solution solution;
vector num = {1,2,3,1};
//vector num = {4,3,3,1};
//vector num = {2,3,1,4,2,1};
int result = solution.findPeakElement(num);
// 輸出
cout<【分析三】
遞歸版
【代碼三】
/*------------------------------------
* 日期：2015-01-31
* 作者：SJF0115
* 題目: 162.Find Peak Element
* 網址：www.2cto.com
* 結果：AC
* 來源：LeetCode
* 博客：
---------------------------------------*/
#include
#include
#include
using namespace std;
class Solution {
public:
int findPeakElement(const vector &num) {
return helper(num,0,num.size()-1);
}
private:
int helper(const vector &num,int left,int right){
// only one element
if(left == right){
return left;
}//if
// neighbor
if(left == right - 1){
return num[left] > num[right] ? left : right;
}//if
int mid = left + (right - left) / 2;
// If num[i-1] < num[i] > num[i+1], then num[i] is peak
if(num[mid] > num[mid-1] && num[mid] > num[mid+1]){
return mid;
}//if
// If num[i-1] > num[i], then num[0...i-1] must contains a peak
if(num[mid] < num[mid - 1]){
return helper(num,left,mid - 1);
}//if
// If num[i-1] < num[i],then num[i+1...n-1] must contains a peak
else{
return helper(num,mid + 1,right);
}//else
}
};
int main(){
Solution solution;
//vector num = {1,2,3,1};
//vector num = {4,3,3,1};
vector num = {2,3,1,4,2,1};
int result = solution.findPeakElement(num);
// 輸出
cout<
