leetcode:Find Peak Element

leetcode:Find Peak Element

一、 題目

峰值元素的定義是比鄰居元素都大的元素。

給定一個數組，其中array[n] != array[n + 1]，找出峰值元素並返回它的索引。但是其中可能含有多個峰值，不過返回其中的一個就可以了，可以假設num[-1] = num[n] = 負無窮大。

例如，[1,2,3,1],3就是峰值，返回索引2。

二、 分析

方法一：www.Bkjia.com

暴力，其實這個方法還可以吧，如果是一般的對稱情況，例如[1,2,3,4,3,2,1]，也就是遍歷一半，而且根據這種思路，方法很多，主要是變形，不過主題思想還是一樣的。

class Solution {
public:
    int findPeakElement(const vector &num) {
        int n = num.size();
        for(int i=1; i < n; i++){
            if(num[i] < num[i-1])
                return i-1;
        }
        return n -1;
    }
};

class Solution {
public:
    int findPeakElement(const vector &num) {
        int n = num.size();
        for(int i = 0; i < n; i++){
            if((i == 0 || num[i] > num[i - 1]) && (i == n-1 || num[i] > num[i + 1]))
                return i;
        }
        return -1;
    }
};

class Solution {
public:
    int findPeakElement(const vector &num) {
        int n = num.size();
        for(int i=1; i < n; i++){
            if(num[i] > num[i-1] && (num[i] > num[i+1] || i == n-1))
                return i;
        }
        return 0;
    }
};

方法二：

二分法，其實也就是和數組中找出一個元素的情況差不多，不過是判斷的條件不一樣罷了。還有這種思路又有兩種方法，一是一直二分二分直到left == right；另一種是找出符合的值就直接返回。

如下：

class Solution {
public:
    int findPeakElement(const vector &num) {
        int left = 0, right = num.size() - 1;
        int mid;
        while(left <= right){
            mid = (left + right)/2;
            if((mid == 0 ||num[mid] > num[mid - 1]) && (num[mid] > num[mid + 1] || mid == num.size() -1))
                return mid;
            else if( mid > 0 && num[mid-1] > num[mid])
                right = mid - 1;
            else 
                left = mid + 1;
        }
        return 0;
    }
};

class Solution {
public:
    int findPeakElement(const vector &num) {
        int left = 0, right = num.size() - 1;
        int mid;
        while(left <= right){
            if(left == right)
                return left;
            mid = (left + right)/2;
            if(num[mid] < num[mid + 1])
                left = mid + 1;
            else
                right = mid;
        }
    }
};