[leetcode] 162. Find Peak Element

[leetcode] 162. Find peak element

Description

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

Given an input array nums, where nums[i] ≠ nums[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 nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]Output: 2Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]Output: 1 or 5 Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Note:

Your solution should be in logarithmic complexity.

分析

题目的意思是：找出一个数组中的peak元素，peak元素要比相邻的元素大。

题目要求log复杂度，只能二分查找了。由于只是需要找到任意一个峰值，那么我们在确定二分查找折半后中间那个元素后，和紧跟的那个元素比较下大小，如果大于，则说明峰值在前面，如果小于则在后面。这样就可以找到一个峰值了.

代码

class Solution {public: int findPeakElement(vector& nums) { int left=0; int right=nums.size()-1; while(left

参考文献

[LeetCode] Find Peak Element 求数组的局部峰值]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。