https://leetcode.com/problems/find-peak-element/
给定一个无序数组,且nums[i] != nums[i+1],找出其中的peak元素,即比左右两边的元素都要大的元素,可以假设nums[-1] 和nums[n]都是负无穷,如果存在多个peak,只需要返回一个就行
------------------------------------------------------------------------------------------------------------------------------------
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.
1. Sequential Search
class Solution {
public:
int findPeakElement(vector<int>& nums) {
for (int i = 1; i < nums.size(); ++i)
{
if (nums[i] < nums[i-1])// 前面都是顺序,只要出现一个逆序对就是peak
return i-1;
}
return nums.size()-1;//如果前面全部都是顺序,那么最后一个数与倒数第二个较小的数以及虚拟的负无穷组成peak.
}
};
提交结果
Runtime: 4 ms, faster than 96.57% of C++ online submissions for Find Peak Element.
Memory Usage: 6.3 MB, less than 100.00% of C++ online submissions for Find Peak Element.
2. 递归减治
class Solution {
public:
int decrease_conquer(vector<int>& nums, int lo, int hi)
{
if (lo==hi)
return lo;
int mi = (lo + hi)>>1;
if(nums[mi]<nums[mi+1])
return decrease_conquer(nums, mi+1, hi);
else
return decrease_conquer(nums, lo, mi);
}
int findPeakElement(vector<int>& nums) {
return decrease_conquer(nums, 0, nums.size()-1);
}
};
提交结果
Runtime: 4 ms, faster than 96.57% of C++ online submissions for Find Peak Element.
Memory Usage: 6.3 MB, less than 100.00% of C++ online submissions for Find Peak Element.
3. 迭代减治
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int lo = 0, hi = nums.size()-1;
while(lo < hi)
{
int mi = (lo + hi)>>1;
if(nums[mi]<nums[mi+1])
lo=mi+1;
else
hi=mi;
}
return lo;
}
};
提交结果
Runtime: 4 ms, faster than 96.57% of C++ online submissions for Find Peak Element.
Memory Usage: 6.3 MB, less than 100.00% of C++ online submissions for Find Peak Element.
-----------------------------------------------------------------------------------------------------------------------------
关于其可以使用减治来代替分治的的原因:
按理来说,在这个无序数组中,峰值可能存在左边,也可能存在右边,为什么这里可以只选择左边或者右边就可以实现?
- 首先明确一点,对于
nums[i]!=nums[i-1]
的数组,肯定是存在峰值元素的,可以尝试构建如下:
__ ___ ___ ___ ___
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 ALLOWED - 我们在
nums[mi]<nums[mi+1]
时,执行lo = mi+1
,此后可以发现,lo 是大于 lo -1的,也就是说,从 lo -1 到 lo 是一个上升趋势 - 由于不存在 nums[i]==nums[i+1] 的情况,因此另外一种情况就是,
nums[mi]>nums[mi+1]
,我们执行hi=mi
,此后可以发现,hi (此时已经等于 mi)是大于 hi + 1 (此时为 mi +1)的,因此从 hi 到 hi + 1 是一个下降趋势 - 最后,从 lo -1 到 lo ,再到 hi 到 hi + 1 是一个先上升后下降的趋势,因此肯定存在峰值,当迭代循环到 lo 和 hi 相等时,lo-1 --> lo(hi) --> lo +1(hi+1),就是一个先上升后下降的过程,因此,lo 就是峰值所在。
此段讨论结果来自与小伙伴 肖同学 的讨论。
网友评论