LeetCode162. Find Peak Elemente（二分）
- Medium
- Accepted：217,525
- Submissions：534,217
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: 2
Explanation: 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.
链接
https://leetcode.com/problems/find-peak-element/
题意
A peak elemen是指比它相邻元素大的元素，现给定一个数组，保证相邻元素不相等，找到其中的任意一个peak elemen并返回下标，假定nums[-1] = nums[n] = -∞。
题解
- 暴力做法，直接遍历挨个判断即可，这里考虑一个问题：当相邻元素不相等且边界元素无穷小时，对于
a[i] a[i+1] a[i+1]三个元素，i从0开始，如果a[i] > a[i+1]，那么a[i]就符合条件了，因为如果a[i] < a[i+1]，那么只需判断a[i+1]是否大于a[i+2]，因此在遍历时只需判断a[i]是否大于a[i+1]即可。时间复杂度$O(n)$ - 考虑到数组部分有序的特点（不存在相等关系部分递增部分递减），我们可以使用二分来找到一个局部的最大值，该值为一个区域的边界，具体做法是对于当前元素a[mid]，如果a[mid]<a[mid+1]，那么就往右办部分找局部最大值，否则往左半部分找局部最大值，时间复杂度$O(logn)$
- 关于数组未排序为什么能使用二分查找详细解释参考文末
代码
- Runtime: 8 ms, faster than 99.42% of C++ online submissions for Find Peak Element.
- Memory Usage: 9 MB, less than 17.56% of C++ online submissions for Find Peak Element.
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r)
{
int m = l + (r - l) / 2;
if (nums[m] < nums[m+1])
l = m + 1;
else if (nums[m] > nums[m+1])
r = m;
}
return l;
}
};参考
The array is not sorted and you cannot just throw half of your search space. But this particular Binary Search Approach still works.
Firstly see Mountain Number leetcode question. Both questions have the exactly same solution
Solution of Same: https://leetcode.com/problems/peak-index-in-a-mountain-array/discuss/181225/CPP-Solution
The reason that Binary Search works here:
- Both the sides of array have INT_MIN as the terminal. This means that even if you keep throwing half of the array in each search..you will always end up in one of the corner
1a. You will reach first element with second number smaller than it
1b. OR you will reach last element with second last element smaller than it
In both the cases the answer will be either the first or the last element respectively since its sure they have INT_MIN on the other side - No two adjacent elements are same
Lets try to construct one array which will not have the corner element as the answer:
-∞ __ ___ ___ ___ ___ -∞
-∞ 1 2 __ ___ ___ 2 1 -∞ (This makes sure that the corner element is not the answer)
-∞ 1 2 3 4 ___ 4 3 2 1 -∞ (Just trying to put answer away from corner)
-∞ 1 2 3 4 5 4 3 2 1 -∞ (But at one time i will have to put a number which is the peak since) SINCE NO ADJACENT SAME ALLOWEDNow lets try solving this
| 1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|
| l | _ | _ | _ | m | _ | _ | _ | r |
a[m] > a[m+1] -> r=m (Not m-1 since m is larger and it itself can be the answer)
| 1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|
| l | m | _ | _ | r | X | X | X | X |
a[m] < a[m+1] -> l = m+1 (Since m is smaller than m+1, m will for sure be not the answer)
| 1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|
| X | X | l | m | r | X | X | X | X |
a[m] < a[m+1] -> l = m+1 (Since m is smaller than m+1, m will for sure be not the answer)
| 1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|-----|---|---|---|---|
| X | X | X | X | l,r | X | X | X | X |
l is the answerThe end.
2019年3月2日 星期六