美文网首页
find-peak-element

find-peak-element

作者: 小王同学加油 | 来源:发表于2018-12-23 13:55 被阅读15次

    相关阅读:

    微信平台:153. Find Minimum in Rotated Sorted Array
    简书:153. Find Minimum in Rotated Sorted Array

    162. 寻找峰值

    1. 描述

    峰值元素是指其值大于左右相邻值的元素。
    给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。
    数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
    你可以假设 nums[-1] = nums[n] = -∞。

    2. 理解

    • 元素是否整体有序--no
      不是整体有序无法采用折半查找,直接查找不容易解决
    • 可以采用顺序遍历 命中特征是什么?
      峰值元素是指其值大于左右相邻值的元素 这个不是充分条件
      假如是最后一个元素,考虑最后一个元素越界问题。
      假如 相同元素 比较没有作用,顺序遍历需要做很多判断
    • 假如数组i 随便一个元素,i-1 必然存在(数组元素大约等于2)
      i+1不确定了

    array(i)>array(i-1)

    这说明array(i-1)肯定不是peak ,因为还有比他大的
    array(i)又可能是

    array(i)<array(i-1)

    array(i)肯定不是最大值,
    array(i-1)又可能是

    array(i)==array(i-1)
    无法排除了,左右2个都可能出现。
    还是根据题目要求寻找peak元素就是最大的。

    • 元素相同的时候,还是两两比较。小的肯定不是
      array[begin] <=array[i] array[begin] 肯定不是

    array[end] <=array[i] array[end] 肯定不是

    • 剩余的元素就是答案 最简单情况 only one

    3. 测试

    1. 数据相等


      image.png
    2. 简单数据


      image.png
      升序

    4. code

    c++
    class Solution {
    public:
        int findPeakElement(vector<int>& nums) {
         
            int begin=0;
            int end =nums.size()-1;
            int mid=0;
            while((end-begin)>1){
                mid=(begin+end)/2;
                
                if (nums[mid]>nums[mid-1]){
                    begin=mid;
                }else if(nums[mid]<nums[mid-1]) {
                    end=mid-1;
                }else if(nums[mid] ==nums[mid-1]){
                    if (nums[mid] >=nums[begin])
                    {
                        begin++;
                    }
                     
                    if (nums[mid] >=nums[end])
                    {
                        end--;
                    }    
                }
                
            }
            
            return nums[begin]>=nums[end]?begin:end; 
        }
    };
    执行用时: 4 ms, 在Find Peak Element的C++提交中击败了99.63% 的用户
    

    go

    /**
    time:nlog(n)
    space:o(1)
    执行用时: 4 ms, 在Find Peak Element的Go提交中击败了100.00% 的用户
    **/
    func findPeakElement(nums []int) int {
        start:=0;
        end:=len(nums)-1;
        mid:=0
        //quit
        for (end-start)>1{
            mid=(start+end)/2
            if nums[mid]>nums[mid-1]{
                start=mid//升序特点 array(mid)>array(mid-1)>array(mid-2)
            }else if  nums[mid]<nums[mid-1]{
                end=mid-1; //降序特点 array(mid)<array(mid-1)<array(mid-2)
            }else if   nums[mid]<nums[mid-1]{
                //仍然使用排除法
                if nums[mid]>=nums[start]{
                    start=start+1
                }
                if nums[mid]>=nums[end]{
                    end=end-1;
                }
            }
            
        }
        
        if nums[start]>=nums[end]{
            return start
        }
        return end
    }
    

    相关文章

      网友评论

          本文标题:find-peak-element

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