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.
Your solution should be in logarithmic complexity.
题目标签:Array, Binary Search
Java Solution:
Runtime beats 31.71%
完成日期:08/31/2017
关键词:Array, Binary search,
关键点:4种可能性来判断峰值的位置
class Solution
{
public int findPeakElement(int[] nums)
{
int left = 0;
int right = nums.length -1; while(left < right - 1)
{
int mid = left + (right - left) / 2;
// if find peak number
if(nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1])
return mid;
else if(nums[mid-1] < nums[mid] && nums[mid] < nums[mid+1])
{ // if find ascending three numbers, the peak number must be in [mid+1, n-1]
left = mid + 1;
}
else if(nums[mid-1] > nums[mid] && nums[mid] > nums[mid+1])
{ // if find descending three numbers, the peak number must be in [0, mid-1]
right = mid - 1;
}
else if(nums[mid-1] > nums[mid] && nums[mid] < nums[mid+1])
{ // if find the mid number is smaller than both neighbors, meaning both sides have peak number
right = mid - 1;
}
} return nums[left] > nums[right]? left:right;
}
}
参考资料:
https://discuss.leetcode.com/topic/5848/o-logn-solution-javacode/14
LeetCode 算法题目列表 - LeetCode Algorithms Questions List