[LeetCode]162.Find Peak Element

【题目】

A peak element is an element that is greater than its neighbors.

Given an input array wherenum[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 thatnum[-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
*   网址：https://oj.leetcode.com/problems/find-peak-element/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findPeakElement(const vector<int> &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<int> num = {1,2,3,1};
    //vector<int> num = {4,3,3,1};
    vector<int> num = {1,2,3,4};
    int result = solution.findPeakElement(num);
    // 输出
    cout<<result<<endl;
    return 0;
}

【分析二】

根据给出的条件： 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 <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        int findPeakElement(const vector<int> &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<int> num = {1,2,3,1};
        //vector<int> num = {4,3,3,1};
        //vector<int> num = {2,3,1,4,2,1};
        int result = solution.findPeakElement(num);
        // 输出
        cout<<result<<endl;
        return 0;
    }

【分析三】

递归版

【代码三】

    /*------------------------------------
    *   日期：2015-01-31
    *   作者：SJF0115
    *   题目: 162.Find Peak Element
    *   网址：https://oj.leetcode.com/problems/find-peak-element/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        int findPeakElement(const vector<int> &num) {
            return helper(num,0,num.size()-1);
        }
    private:
        int helper(const vector<int> &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<int> num = {1,2,3,1};
        //vector<int> num = {4,3,3,1};
        vector<int> num = {2,3,1,4,2,1};
        int result = solution.findPeakElement(num);
        // 输出
        cout<<result<<endl;
        return 0;
    }