【刷题之路Ⅱ】牛客 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、代码实现一、题目描述 原题连接: NC107 寻找峰值 题目描…...
智能灯泡一Homekit智能家居系列
传统的灯泡是通过手动打开和关闭开关来工作。有时,它们可以通过声控、触控、红外等方式进行控制,或者带有调光开关,让用户调暗或调亮灯光。 智能灯泡内置有芯片和通信模块,可与手机、家庭智能助手、或其他智能硬件进行通信&#…...
外包离职,历时学习416天,成功上岸百度,分享成长过程~
前言: 没有绝对的天才,只有持续不断的付出。对于我们每一个平凡人来说,改变命运只能依靠努力幸运,但如果你不够幸运,那就只能拉高努力的占比。 2020年7月,我有幸成为了百度的一名Java后端开发,…...
利用客户支持建立忠诚度和竞争优势
客户支持可以极大地改变您的业务;最细微、最微妙的差异都会使拥有一次性客户和拥有终身客户之间产生差异。在这篇博文中,我们将揭示客户对企业的忠诚度的三种核心类型,以及如何利用强大的客户支持工具和原则来提高理想的忠诚度并获得决定性的竞争优势。一…...
看他人代码小总结
针对几个功能类似的函数: 1.需要经常调试则定义一个参数比如is_debug来选择是否在调试,定义一些参数专门用于调试用,不用每次都修改这些参数,只需要修改is_debug这个参数; 2.把其中的变量(常量)单独拎出来放到一个文件…...
cudaMemGetInfo()函数cudaDeviceGetAttribute()函数来检查设备上的可用内存
使用CUDA Runtime API中的cudaMemGetInfo()函数来检查设备上的可用内存。该函数将返回当前可用于分配的总设备内存大小和当前可用于分配的最大单个内存块大小。 示例代码,演示了如何在分配内存之前和之后调用cudaMemGetInfo()函数来检查可用内存 size_t free_byte…...
【基础阶段】01中华人民共和国网络安全法
文章目录1 网络安全行业介绍2 什么是黑客和白帽子3 网络安全课程整体介绍4 网络安全的分类5 常见的网站攻击方式6 安全常见术语介绍7 《网络安全法》制定背景和核心内容8 《全国人大常委会关于维护互联网安全的决定》9《中华人民共和国计算机信息系统安全保护条例》10 《中华人…...
隐私计算领域大咖推荐,这些国内外导师值得关注
开放隐私计算 经过近一个月的信息收集,研习社已经整理了多位国内外研究隐私计算的导师资料。邻近考研复试,研习社希望小伙伴们能够通过本文整理的信息,选择自己心仪的老师,在研究生的路途上一帆风顺!1. 国内隐私计算导…...
009 uni-app之vue、vuex
vue.js 视频教程 vue3.js 中文官网 vue.js 视频教程 vue语法:https://uniapp.dcloud.net.cn/tutorial/vue-vuex.html vue2迁移到 vue3: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:固定的公网IP地址 4、SNAT转换2:非固定的公网IP地址(共享动态IP地址) 二、SNAT实验 配置web服务…...
递归理解三:深度、广度优先搜索,n叉树遍历,n并列递归理解与转非递归
参考资料: DFS 参考文章BFS 参考文章DFS 参考视频二叉树遍历规律递归原理源码N叉树规律总结: 由前面二叉树的遍历规律和递归的基本原理,我们可以看到,二叉树遍历口诀和二叉树递推公式有着紧密的联系 前序遍历:F(x…...
MATLAB 2023a安装包下载及安装教程
[软件名称]:MATLAB 2023a [软件大小]: 12.2 GB [安装环境]: Win11/Win 10/Win 7 [软件安装包下载]:https://pan.quark.cn/s/8e24d77ab005 MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。行矩阵运算、绘制函数和数据、实现算…...
QT学习开发笔记(数据库之实用时钟)
数据库 数据库是什么?简易言之,就是保存数据的文件。可以存储大量数据,包括插入数据、更 新数据、截取数据等。用专业术语来说,数据库是“按照数据结构来组织、存储和管理数据的 仓库”。是一个长期存储在计算机内的、有组织的、…...
Docker常规安装简介
总体步骤 搜索镜像拉取镜像查看镜像启动镜像,服务端口映射停止容器移除容器 案例 安装tomcat docker hub上面查找tomcat镜像,docker search tomcat从docker hub上拉取tomcat镜像到本地 docker pull tomcatdocker images查看是否有拉取到的tomcat 使用tomcat镜像创…...
Python - PyQT5 - ui文件转为py文件
在QTdesigner图形化编辑工具中,有些控件我们是可以直接在编辑界面进行编辑的,有些是不可以编辑的,只能通过Python代码进行编辑,不过总体来说,所有能够通过图形化编辑界面可以编辑的,都可以通过Python语言实…...
分布式事务和分布式锁
1、关于分布式锁的了解? 原理:控制分布式系统有序的去对共享资源进行操作,通过互斥来保持一致性。 具备的条件: ①分布式环境下,一个方法在同一时间只能被一个机器的一个线程执行 ②高可用的获取锁和释放锁 ③高性能…...
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),把对象的创建和对象之间的调用过程,交给Spring进行管理。 (2)使用IOC目的&…...
路科验证UVM入门与进阶详解实验0
一.代码编译 首先创建新项目,导入lab0 的UVM文件; 针对uvm_compile文件,先进行编译; 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负责的一个项目占用不断增加,差点搞崩服务器(╥﹏╥)……一下子有点懵,不能立刻确定是哪里导致的问题,所以决定好好研究下这个之前一直被我忽视的问题诊断工具🔧——JVisualVM嘿嘿我…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...
【Veristand】Veristand环境安装教程-Linux RT / Windows
首先声明,此教程是针对Simulink编译模型并导入Veristand中编写的,同时需要注意的是老用户编译可能用的是Veristand Model Framework,那个是历史版本,且NI不会再维护,新版本编译支持为VeriStand Model Generation Suppo…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
