现在的位置: 首页 > 综合 > 正文

leetcode:Find Peak Element

2019年11月02日 ⁄ 综合 ⁄ 共 1333字 ⁄ 字号 评论关闭

一、 题目

峰值元素的定义是比邻居元素都大的元素。

给定一个数组,其中array[n] != array[n + 1],找出峰值元素并返回它的索引。但是其中可能含有多个峰值,不过返回其中的一个就可以了,可以假设num[-1] = num[n] = 负无穷大。

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

二、 分析

方法一:

暴力,其实这个方法还可以吧,如果是一般的对称情况,例如[1,2,3,4,3,2,1],也就是遍历一半,而且根据这种思路,方法很多,主要是变形,不过主题思想还是一样的。

 

class Solution {
public:
    int findPeakElement(const vector<int> &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<int> &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<int> &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<int> &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<int> &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;
        }
    }
};

 

抱歉!评论已关闭.