• 【21天学习挑战赛】二分查找题目之寻找峰值



    活动地址:CSDN21天学习挑战赛

    ⛲162. 寻找峰值

    峰值元素是指其值严格大于左右相邻值的元素。

    给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。

    你可以假设 nums[-1] = nums[n] = -∞ 。

    你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

    示例 1:

    输入:nums = [1,2,3,1]
    输出:2
    解释:3 是峰值元素,你的函数应该返回其索引 2。

    来源:力扣(LeetCode)
    链接:https://leetcode.cn/problems/find-peak-element
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    🎢顺序查找

    直接从第1个元素找到最后一个元素,nums[i-1]nums[i+1],即为峰值

    class Solution {
        public int findPeakElement(int[] nums) {
            int n=nums.length;
            if(n<2){
                return 0;
            }
            if(nums[0]>nums[1]){
                return 0;
            }
            if(nums[n-1]>nums[n-2]){
                return n-1;
            }
            for(int i=1;i<n-1;i++){
                if(nums[i]>nums[i-1]&&nums[i]>nums[i+1]){
                    return i;
                }
            }
            return -1;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    🚍时间复杂度

    因为最差情况是找到尾部,因此时间复杂度为O(n2)
    这种解题方法不行,必须要用二分查找才能符合题意

    🚂二分查找

    我们都知道二分查找的条件是数组要有序
    这个数组并非有序,那么我们是否不能用二分查找呢
    数组有序只是二分查找的一个充分非必要条件
    并非有序数组才能二分
    只要这个数组存在某种规律,能让数组分成两部分,并且只用在其中的一部分查找

    在这一题中,我们发现峰值左右两边的数必定比峰值小
    那么我们是否可以用这个规律来定义二分的规则呢
    如果中间的数大于右边的数,那么峰值必定在左边,
    反之,就在右边

    class Solution {
        public int findPeakElement(int[] nums) {
            int l=0,r=nums.length-1;
            while(l<r){
                int m=l+(r-l)/2;
                
                if(nums[m]>nums[m+1]){
                    r=m;
                }else{
                    l=m+1;
                }
            }
            return l;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
  • 相关阅读:
    【English】joy vs joyfulness
    基于WPF技术的换热站智能监控系统09--封装水泵对象
    Ceph的认证授权
    【Linux】解决缓存锁问题:无法获得锁 /var/lib/dpkg/lock-frontend
    设计模式---策略模式
    mysql八股
    Golang结构体
    深入理解JVM虚拟机第四篇:一些常用的JVM虚拟机
    【软件与系统安全】AFL模糊测试实验
    嵌入式Linux应用开发基础知识——GCC编译过程
  • 原文地址:https://blog.csdn.net/xiaolu567/article/details/126237527