美文网首页
162. Find Peak Element

162. Find Peak Element

作者: 默写年华Antifragile | 来源:发表于2020-03-20 19:13 被阅读0次

    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]的数组,肯定是存在峰值元素的,可以尝试构建如下:
      -\infty __ ___ ___ ___ ___ -\infty
      -\infty 1 2 __ ___ ___ 2 1 -\infty (This makes sure that the corner element is not the answer)
      -\infty 1 2 3 4 ___ 4 3 2 1 -\infty (Just trying to put answer away from corner)
      -\infty 1 2 3 4 5 4 3 2 1 -\infty (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 就是峰值所在。

    此段讨论结果来自与小伙伴 肖同学 的讨论。

    相关文章

      网友评论

          本文标题:162. Find Peak Element

          本文链接:https://www.haomeiwen.com/subject/ylfsyhtx.html