查找峰值元素_超悦人生的博客-程序员宝宝_峰值元素

技术标签: # 二分查找  二分查找  数组  # 数组  算法题目  

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

  • 解决方案

利用二分查找来解决,注意二分查找不一定要去数组有序,而是只要能满足某种规律,能够判断要在左半部分还是右半部分查找即可。即对于任何一个相同元素不同的数组,只要满足nums[1]>nums[0],nums[nums.length-2]>nums[nums.length-1],则其中必定会存在峰值。利用这个特点进行二分查找,对于mid位置的元素,有以下几种情况:1.若mid位置元素与相邻元素形成V字形,则查找左半部分,2.若是倒置的V字形,则返回改点即可3.若是递减的,则继续查找左半部分4.若是递增的,则返回右半部分继续查找。代码如下:

public static int findPeakElement(int[] nums){
    
        int left = 1;
        int right = nums.length - 2;
        while(left <= right){
    
            int middle = left + ((right - left) >> 1);
            if(nums[middle] < nums[middle - 1] && nums[middle] < nums[middle + 1])
                right = middle + 1;
            else if(nums[middle] > nums[middle - 1] && nums[middle] > nums[middle + 1])
                return middle;
            else if(nums[middle] > nums[middle - 1] && nums[middle] < nums[middle + 1])
                left = middle + 1;
            else if(nums[middle] < nums[middle - 1] && nums[middle] > nums[middle + 1])
                right = middle - 1;
        }
        return -1;
    }
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zjbzlc/article/details/100856316

智能推荐

Maven企业级应用(四) 之依赖管理机制_喵了个汪q的博客-程序员宝宝_企业maven依赖管理

1、依赖引入的方式可以用如下方式引入依赖&lt;dependency&gt; &lt;groupId&gt;&lt;/groupId&gt; &lt;artifactId&gt;&lt;/artifactId&gt; &lt;version&gt;&lt;/version&gt; &lt;type&gt;&lt;/type&gt; &lt;scope&gt;&lt;/scope&gt; &lt;optional&gt;&lt;/optional&gt;&lt;/dependency&gt;

ORA-01008: not all variables bound_lijun123123的博客-程序员宝宝

ORA-01008: not all variables bound ORA-01008: not all variables bound 这个异常是因为SQL语句中的 ? 没有被传参数导致的。

Elasticsearch 实战(一、基本概念与安装使用)_绿水本无忧d的博客-程序员宝宝

Elasticsearch作用: 快速存储、搜索和分析海量数据。基本概念Index 索引: 类似 MySQL 中的 Insert,指插入(索引)一条数据;也可以类似为 MySQL 中的 Database,一个数据库(索引)。Type: 类似于 MySQL 中的 table,可以理解成一张表(一个类型)。Document: 一条记录,以 json 格式存储。安装使用 Docker 安装命令中含有注释,请勿直接复制粘贴下载docker pull elasticsearch:7.4.2配

每个程序员都应该学习的5种编程语言_weixin_43875545的博客-程序员宝宝

了解一种或者真正的编码语言是很好的,但作为一个真正的多语言开发人员是如何实现真正的主要状态。我在某处读到程序员应该每年学习一种新的编程语言(我认为它的代码完整,但不确定),但如果你不能这样做,我建议你至少学习以下五种编程语言,以便在你的职业生涯中取得好成绩。 。每个公司都喜欢多语言程序员和一个全面的编码人员,他们是多才多艺的语言编写快速脚本,并且还可以编写复杂的Java程序,确实是一个有价值的...

Davies-Bouldin指数(DBI)_Rainylt的博客-程序员宝宝_dbi指数matlab代码

参考http://blog.sina.com.cn/s/blog_65c8baf901016flh.html用途:聚类算法中评估判断簇的个数是否合适(用来选择k)原理:计算所有簇的类内距离和类间距离的比值(类内/类间),比值越小越好。即希望类间距离越大,类内距离越小(数据越集中)越好公式:(1)分散度(类内距离)Si:表示第i个类中,度量数据点的分散程度(2)类间距离Mij:表示第i类中心与第j类中心的距离(3)两类的相似度:其实就是分散度/类间距离越分散,类间距离越小,相似度越大(

android拍照功能无预览,Android快速实现无预览拍照功能_杯中水8033的博客-程序员宝宝

Android快速实现无预览拍照功能camerakit:ckFacing="front" 表示用前置摄像头,其他属性请参照官方文档。注意:宽高不能设置为0,否则不能拍照。3、Java代码public class MainActivity extends BaseActivity {@BindView(R.id.btn_test)Button btnTest;@BindView(R.id.camer...

随便推点

火了,挡不住了:Facebook Move编程语言入门_元宇宙iwemeta的博客-程序员宝宝_move编程语言

火了,挡不住了:Facebook Move编程语言入门Facebook区块链项目Libra的其中一个技术亮点,就是它使用了一种称为Move的新编程语言,那么这种语言是怎样的呢,今天我们就从其官方的概述资料入手,近距离了解这种新的语言。以下内容为译文:Move是一种新的编程语言,它为Libra区块链提供了一个安全和可编程的基础。Libra区块链中的账户是任意数量Move资源及Move模块的容...

Python调用外部程序——os.system()和subprocess.call_ailsa0503的博客-程序员宝宝

通过os.system函数调用其他程序预备知识:cmd中打开和关闭程序cmd中打开程序a.打开系统自带程序系统自带的程序的路径一般都已加入环境变量之中,只需在cmd窗口中直接输入程序名称即可。以notepad为例,直接在cmd窗口中输入notepad后回车即可打开。b.打开自己安装且没有加入环境变量的程序以网易云音乐为例...

Android5.0,6.0,7.0,8.0新特性整理_感同身受ing的博客-程序员宝宝

转Android5.0,6.0,7.0,8.0新特性整理2017年08月31日 00:01:00 锐心凌志 阅读数:9654更多个人分类: Android背景Android5.0(Android Lollipop)是谷歌公司2014年10月发布的全新安卓系统,至今已经两年多。然而由于国产手机对安卓ROM的深度定制或修改,以及手机厂商、芯片制造商、运营商之间错综复杂的关系,我们更...

IOS集成支付宝回调的坑_kingtaxin的博客-程序员宝宝

最近做个项目需要集成支付,当然选用支付宝,但是过程中发现了巨大的坑支付完成后,在appdelegate中作回调,但是这个是不会执行- (BOOL)application:(UIApplication *)application openURL:(NSURL *)url sourceApplication:(NSString *)sourceApplication annotation:

python和tkinter实现摄像头实时无闪烁显示_zeroty的博客-程序员宝宝_python tkinter 摄像头

摄像头显示者tkinter段canvas中很简单,但要无闪烁,就要弄很久。后来,发现,其实就一句话,也不知道为啥,反正在creat_image之后,加上obr就可以,即类似:canvas_img.create_image(0, 0, anchor = NW ,image = cam_imageTk) obr = cam_imageTk 不多说了,上全部代码:from tkinter import *import tkinter as tkfrom PIL import

桐花万里python路-高级篇-并发编程-03-线程_weixin_30340819的博客-程序员宝宝

理论进程只是一个资源单位,线程才是cpu上的执行单位无需申请空间,创建开销小共享和创建开销多线程共享一个进程的地址空间线程比进程更轻量级,线程比进程更容易创建可撤销I/O密集型,多线程,会加快程序执行的速度在多cpu系统中,为了最大限度的利用多核,可以开启多个线程,比开进程开销要小的多。(这一条并不适用于python)线程操作...

推荐文章

热门文章

相关标签