当前位置: 首页 > news >正文

【刷题之路Ⅱ】牛客 NC107 寻找峰值

【刷题之路Ⅱ】牛客 NC107 寻找峰值

  • 一、题目描述
  • 二、解题
    • 1、方法1——直接遍历
      • 1.1、思路分析
      • 1.2、代码实现
    • 2、方法2——投机取巧的求最大值
      • 2.1、思路分析
      • 2.2、代码实现
    • 3、方法3——二分法
      • 3.1、思路分析
      • 3.2、代码实现

一、题目描述

原题连接: NC107 寻找峰值

题目描述:
给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] =−∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗?
数据范围:1≤nums.length≤2×10^5
-231<=nums[i]<=231 −1

示例1
输入:[2,4,1,2,7,8,4]
返回值: 1
说明:4和8都是峰值元素,返回4的索引1或者8的索引5都可以

示例2
输入:[1,2,3,1]
返回值: 2
说明:3 是峰值元素,返回其索引 2

二、解题

1、方法1——直接遍历

1.1、思路分析

我们可以直接遍历数组,但有两个情况需要特殊考虑。
当i等于0时,判断nums[i]是否大于nums[i + 1],若大于,则返回i;
当i等于numsLen - 1时,判断nums[i]是否大于nums[i - 1],若大于,则返回i;
其他情况判断是否有nums[i] > nums[i - 1] && nums[i] > nums[i + 1],如果成立,则返回i。

1.2、代码实现

有了以上思路,那我们写起代码来也就水到渠成了:

int findPeakElement1(int* nums, int numsLen) {assert(nums);if (1 == numsLen) {return 0;}int i = 0;for (i = 0; i < numsLen; i++) {if (0 == i) {if (nums[i] > nums[i + 1]) {return i;}}else if (numsLen - 1 == i) {if (nums[i] > nums[i - 1]) {return i;}}else if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {return i;}}return -1;
}

时间复杂度:O(n),n为数组元素个数。
空间复杂度:O(1),我们只需要用到常数级的额外空间

2、方法2——投机取巧的求最大值

2.1、思路分析

根据题目的描述:“对于所有有效的 i 都有 nums[i] != nums[i + 1]”,且返回任意一个就行。
就有一个非常投机取巧的方法就是直接找到数组中的最大值,返回其下标就行了。
这个方法之所有有效是因为峰值不一定是最大值,但最大值一定是峰值。😏
在这里插入图片描述

2.2、代码实现

有了以上思路,那我们写起代码来也就水到渠成了:

int findPeakElement2(int* nums, int numsLen) {assert(nums);if (1 == numsLen) {return 0;}int max = nums[0];int index = 0;int i = 0;for (i = 1; i < numsLen; i++) {if (nums[i] > max) {max = nums[i];index = i;}}return index;
}

时间复杂度:O(n),n为数组元素个数,我们只需要遍历一遍数组即可。
空间复杂度:O(1),我们只需要用到常数级的额外空间。

3、方法3——二分法

3.1、思路分析

我们其实可以使用二分法来是我们的left和right每一次都向"峰值"靠近。
当left和right重合时即找到了峰值。
具体做法如下:
1、当nums[mid] < nums[mid + 1]时,说明从下标mid到下标mid + 1是在走上坡路:
在这里插入图片描述
则可以肯定此时的mid一定不是峰值,所以执行left = mid + 1,使区间向峰值靠近。
在这里插入图片描述
2、当nums[mid] > nums[mid + 1]时,说明从下标mid到下标mid + 1是在走下坡路:
在这里插入图片描述
则mid可能是峰值,此时应该执行right = mid(不能跳过mid,因为mid可能是峰值),使区间向峰值靠近。
在这里插入图片描述
最后当left和right重合时,说明我们已经找到了峰值。

3.2、代码实现

有了以上思路,那我们写起代码来也就水到渠成了:

int findPeakElement3(int* nums, int numsLen) {assert(nums);int left = 0;int right = numsLen - 1;int mid = 0;while (left < right) {mid = left + (right - left) / 2;if (nums[mid] < nums[mid + 1]) {left = mid + 1;}else {right = mid;}}return left;
}

时间复杂度:O(log2N),其中N为数组元素个数,最坏情况下,我们要对整个数组进行二分,所以时间复杂度为O(log2N)。
空间复杂度:O(1),我们只需要用到常数级的额外空间。

相关文章:

【刷题之路Ⅱ】牛客 NC107 寻找峰值

【刷题之路Ⅱ】牛客 NC107 寻找峰值一、题目描述二、解题1、方法1——直接遍历1.1、思路分析1.2、代码实现2、方法2——投机取巧的求最大值2.1、思路分析2.2、代码实现3、方法3——二分法3.1、思路分析3.2、代码实现一、题目描述 原题连接&#xff1a; NC107 寻找峰值 题目描…...

智能灯泡一Homekit智能家居系列

传统的灯泡是通过手动打开和关闭开关来工作。有时&#xff0c;它们可以通过声控、触控、红外等方式进行控制&#xff0c;或者带有调光开关&#xff0c;让用户调暗或调亮灯光。 智能灯泡内置有芯片和通信模块&#xff0c;可与手机、家庭智能助手、或其他智能硬件进行通信&#…...

外包离职,历时学习416天,成功上岸百度,分享成长过程~

前言&#xff1a; 没有绝对的天才&#xff0c;只有持续不断的付出。对于我们每一个平凡人来说&#xff0c;改变命运只能依靠努力幸运&#xff0c;但如果你不够幸运&#xff0c;那就只能拉高努力的占比。 2020年7月&#xff0c;我有幸成为了百度的一名Java后端开发&#xff0c…...

利用客户支持建立忠诚度和竞争优势

客户支持可以极大地改变您的业务;最细微、最微妙的差异都会使拥有一次性客户和拥有终身客户之间产生差异。在这篇博文中&#xff0c;我们将揭示客户对企业的忠诚度的三种核心类型&#xff0c;以及如何利用强大的客户支持工具和原则来提高理想的忠诚度并获得决定性的竞争优势。一…...

看他人代码小总结

针对几个功能类似的函数&#xff1a; 1.需要经常调试则定义一个参数比如is_debug来选择是否在调试&#xff0c;定义一些参数专门用于调试用&#xff0c;不用每次都修改这些参数&#xff0c;只需要修改is_debug这个参数&#xff1b; 2.把其中的变量(常量)单独拎出来放到一个文件…...

cudaMemGetInfo()函数cudaDeviceGetAttribute()函数来检查设备上的可用内存

使用CUDA Runtime API中的cudaMemGetInfo()函数来检查设备上的可用内存。该函数将返回当前可用于分配的总设备内存大小和当前可用于分配的最大单个内存块大小。 示例代码&#xff0c;演示了如何在分配内存之前和之后调用cudaMemGetInfo()函数来检查可用内存 size_t free_byte…...

【基础阶段】01中华人民共和国网络安全法

文章目录1 网络安全行业介绍2 什么是黑客和白帽子3 网络安全课程整体介绍4 网络安全的分类5 常见的网站攻击方式6 安全常见术语介绍7 《网络安全法》制定背景和核心内容8 《全国人大常委会关于维护互联网安全的决定》9《中华人民共和国计算机信息系统安全保护条例》10 《中华人…...

隐私计算领域大咖推荐,这些国内外导师值得关注

开放隐私计算 经过近一个月的信息收集&#xff0c;研习社已经整理了多位国内外研究隐私计算的导师资料。邻近考研复试&#xff0c;研习社希望小伙伴们能够通过本文整理的信息&#xff0c;选择自己心仪的老师&#xff0c;在研究生的路途上一帆风顺&#xff01;1. 国内隐私计算导…...

009 uni-app之vue、vuex

vue.js 视频教程 vue3.js 中文官网 vue.js 视频教程 vue语法&#xff1a;https://uniapp.dcloud.net.cn/tutorial/vue-vuex.html vue2迁移到 vue3&#xff1a;https://uniapp.dcloud.net.cn/tutorial/migration-to-vue3.html Vuex Vuex 是一个专为 Vue.js 应用程序开发的…...

Linux防火墙——SNAT、DNAT

目录 NAT 一、SNAT策略及作用 1、概述 SNAT应用环境 SNAT原理 SNAT转换前提条件 1、临时打开 2、永久打开 3、SNAT转换1&#xff1a;固定的公网IP地址 4、SNAT转换2&#xff1a;非固定的公网IP地址&#xff08;共享动态IP地址&#xff09; 二、SNAT实验 配置web服务…...

递归理解三:深度、广度优先搜索,n叉树遍历,n并列递归理解与转非递归

参考资料&#xff1a; DFS 参考文章BFS 参考文章DFS 参考视频二叉树遍历规律递归原理源码N叉树规律总结&#xff1a; 由前面二叉树的遍历规律和递归的基本原理&#xff0c;我们可以看到&#xff0c;二叉树遍历口诀和二叉树递推公式有着紧密的联系 前序遍历&#xff1a;F(x…...

MATLAB 2023a安装包下载及安装教程

[软件名称]:MATLAB 2023a [软件大小]: 12.2 GB [安装环境]: Win11/Win 10/Win 7 [软件安装包下载]:https://pan.quark.cn/s/8e24d77ab005 MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。行矩阵运算、绘制函数和数据、实现算…...

QT学习开发笔记(数据库之实用时钟)

数据库 数据库是什么&#xff1f;简易言之&#xff0c;就是保存数据的文件。可以存储大量数据&#xff0c;包括插入数据、更 新数据、截取数据等。用专业术语来说&#xff0c;数据库是“按照数据结构来组织、存储和管理数据的 仓库”。是一个长期存储在计算机内的、有组织的、…...

Docker常规安装简介

总体步骤 搜索镜像拉取镜像查看镜像启动镜像,服务端口映射停止容器移除容器 案例 安装tomcat docker hub上面查找tomcat镜像&#xff0c;docker search tomcat从docker hub上拉取tomcat镜像到本地 docker pull tomcatdocker images查看是否有拉取到的tomcat 使用tomcat镜像创…...

Python - PyQT5 - ui文件转为py文件

在QTdesigner图形化编辑工具中&#xff0c;有些控件我们是可以直接在编辑界面进行编辑的&#xff0c;有些是不可以编辑的&#xff0c;只能通过Python代码进行编辑&#xff0c;不过总体来说&#xff0c;所有能够通过图形化编辑界面可以编辑的&#xff0c;都可以通过Python语言实…...

分布式事务和分布式锁

1、关于分布式锁的了解&#xff1f; 原理&#xff1a;控制分布式系统有序的去对共享资源进行操作&#xff0c;通过互斥来保持一致性。 具备的条件&#xff1a; ①分布式环境下&#xff0c;一个方法在同一时间只能被一个机器的一个线程执行 ②高可用的获取锁和释放锁 ③高性能…...

JAVA-4-[Spring框架]基于XML方式的Bean管理

1 Spring IOC容器 (1)IOC底层原理 (2)IOC接口(BeanFactory) (3)IOC操作Bean管理(基于XML) (4)IOC操作Bean管理(基于注释) 1.1 IOC概念 (1)控制反转(Inversion of Control)&#xff0c;把对象的创建和对象之间的调用过程&#xff0c;交给Spring进行管理。 (2)使用IOC目的&…...

路科验证UVM入门与进阶详解实验0

一.代码编译 首先创建新项目&#xff0c;导入lab0 的UVM文件&#xff1b; 针对uvm_compile文件&#xff0c;先进行编译&#xff1b; module uvm_compile;// NOTE:: it is necessary to import uvm package and macrosimport uvm_pkg::*;include "uvm_macros.svh"in…...

Linux之Shell编程(1)

文章目录前言一、Shell是什么二、Shell脚本的执行方式脚本的常用执行方式三、Shell的变量Shell变量介绍shell变量的定义四、设置环境变量基本语法快速入门五、位置参数变量介绍●基本语法●位置参数变量六、预定义变量基本介绍基本语法七、运算符基本介绍基本语法前言 为什么要…...

Java问题诊断工具——JVisualVM

这篇文章源自一次加班改bug的惨痛经历[,,_,,]:3负责的一个项目占用不断增加&#xff0c;差点搞崩服务器(╥﹏╥)……一下子有点懵&#xff0c;不能立刻确定是哪里导致的问题&#xff0c;所以决定好好研究下这个之前一直被我忽视的问题诊断工具&#x1f527;——JVisualVM嘿嘿我…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...