[LeetCode]162.Find Peak Element

【题目】

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.

【分析一】

我们首先想到的就是时间复杂度为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;
    }