(二分查找)leetcode162. 寻找峰值
文章目录
- 一、题目
- 1、题目描述
- 2、基础框架
- 3、原题链接
- 二、解题报告
- 1、思路分析
- 2、时间复杂度
- 3、代码详解
- 三、本题小知识
一、题目
1、题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1:
输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。
示例 2:
输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5
解释:你的函数可以返回索引 1,其峰值元素为 2;
或者返回索引 5, 其峰值元素为 6。
2、基础框架
- C++版本给出的基础框架如下:
3、原题链接
https://leetcode.cn/problems/find-peak-element/
二、解题报告
1、思路分析
(1)(1)(1)易证,如果nums[i] > nums[i+1]那么[0…i]区间内肯定存在峰值。如果nums[i] < nums[i+1],那么[i…nums.length-1]区间内肯定存在峰值。
(2)(2)(2)所以该问题具有二分性,如果是nums[mid]>nums[mid+1],那么丢弃[i+1…r],即r = mid.
(3)(3)(3)如果nums[mid]<nums[mid+1],那么就丢弃[l…i],即l = mid +1
(4)(4)(4)二分的出口条件是l >= r,即l一旦等于r就会结束循环,所以mid不会大于r,即mid+1不会有越界问题。
2、时间复杂度
时间复杂度为O(logn)
3、代码详解
class Solution {
public:int findPeakElement(vector<int>& nums) {int l = 0;int r = nums.size() - 1;while(l < r) {int mid = l + (r - l) / 2;if (nums[mid] > nums[mid+1]) {r = mid;}else l = mid + 1;}return r;}
};
三、本题小知识
相关文章:
(二分查找)leetcode162. 寻找峰值
文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识一、题目 1、题目描述 峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值…...
spring boot 配合element ui vue实现表格的批量删除(前后端详细教学,简单易懂,有手就行)
目录 一.前言: 二. 前端代码: 2.1.element ui组件代码 2.2删除按钮 2.3.data 2.4.methods 三.后端代码: 一.前言: 研究了其他人的博客,找到了一篇有含金量的,进行了部分改写实现前后端分离࿰…...
hiveSQL开窗函数详解
hive开窗函数 文章目录hive开窗函数1. 开窗函数概述1.1 窗口函数分类1.2 窗口函数和普通聚合函数的区别2. 窗口函数的基本用法2.1 基本用法2.2 设置窗口的方法2.2.1 window_name2.2.2 partition by2.2.3 order by 子句2.2.4 rows指定窗口大小窗口框架2.3 开窗函数中加 order by…...
深度学习基础实例与总结
一、神经网络 1 深度学习 1 什么是深度学习? 简单来说,深度学习就是一种包括多个隐含层 (越多即为越深)的多层感知机。它通过组合低层特征,形成更为抽象的高层表示,用以描述被识别对象的高级属性类别或特征。 能自生成数据的中…...
在 WIndows 下安装 Apache Tinkerpop (Gremlin)
一、安装 JDK 首先安装 Java JDK,这个去官网下载即可,我下载安装的 JDK19(jdk-19_windows-x64_bin.msi),细节不赘述。 二、去 Tinkerpop 网站下载 Gremlin 网址:https://tinkerpop.apache.org/ 点击下面…...
从软件的角度看待PCI和PCIE(一)
1.最容易访问的设备是什么? 是内存! 要读写内存,知道它的地址就可以了,不需要什么驱动程序; volatile unsigned int *p 0xffff8811; unsigned int val; *p val; val *p;只有内存能这样简单、方便的使用吗…...
DSP_TMS320F28377D_ADC学习笔记
前言 DSP各种模块的使用,基本上就是 GPIO复用配置、相关控制寄存器的配置、中断的配置。本文主要记录本人对ADC模块的学习笔记。TMS320F28377D上面有24路ADC专用IO,这意味着不需要进行GPIO复用配置。 只需要考虑相关控制寄存器和中断的配置。看代码请直…...
springcloud3 Nacos中namespace和group,dataId的联系
一 Namespance和group和dataId的联系 1.1 3者之间的联系 话不多说,上答案,如下图: namespance用于区分部署环境,group和dataId用于逻辑上区分两个目标对象。 二 案例:实现读取注册中心的不同环境下的配置文件 …...
[YOLO] yolo理解博客笔记
YOLO v2和V3 关于设置生成anchorbox,Boundingbox边框回归的过程详细解读 YOLO v2和V3 关于设置生成anchorbox,Boundingbox边框回归的个人理解https://blog.csdn.net/shenkunchang1877/article/details/105648111YOLO v1网络结构计算 Yolov1-pytorch版 …...
清华源pip安装Python第三方包
一、更换PIP源PIP源在国外,速度慢,可以更换为国内源,以下是国内一些常用的PIP源。豆瓣(douban) http://pypi.douban.com/simple/ (推荐)清华大学 https://pypi.tuna.tsinghua.edu.cn/simple/阿里云 http://mirrors.aliyun.com/pypi/simple/中…...
python线程池【ThreadPoolExecutor()】批量获取博客园标题数据
转载:蚂蚁学python 网址:【【2021最新版】Python 并发编程实战,用多线程、多进程、多协程加速程序运行】 https://www.bilibili.com/video/BV1bK411A7tV/?p8&share_sourcecopy_web&vd_sourced0ef3d08fdeef1740bab49cdb3e96467实战案…...
LearnOpenGL-入门-8.坐标系统
本人刚学OpenGL不久且自学,文中定有代码、术语等错误,欢迎指正 我写的项目地址:https://github.com/liujianjie/LearnOpenGLProject LearnOpenGL中文官网:https://learnopengl-cn.github.io/ 文章目录坐标系统概述局部空间世界空…...
windows10使用wsl2安装docker
配环境很麻烦,想利用docker的镜像环境跑一下代码整个安装过程的原理是:windows使用docker,必须先安装一个linux虚拟机,才可运行docker,而采用wsl2安装虚拟机是目前最好的方法第一步 windows安装wsl2控制面板->程序-…...
Javascript的API基本内容(六)
一、正则表达式 1.定义规则 const reg /表达式/ 其中/ /是正则表达式字面量正则表达式也是对象 2.使用正则 test()方法 用来查看正则表达式与指定的字符串是否匹配如果正则表达式与指定的字符串匹配 ,返回true,否则false 3.元字符 比如࿰…...
电压放大器和电流放大器的区别是什么意思
在日常电子实验测试中,很多电子工程师都会使用到电压放大器和电流放大器,但是很多新手工程师却无法区分两者的区别,下面就让安泰电子来为我们讲解电压放大器和电流放大器的区别是什么意思。 一、电压放大器介绍: 电压放大器是一种…...
cast提前!最简单有效的神经网络优化方法,没有之一!
做优化有时候真的很头疼,绞尽脑汁的想怎么做算法等价,怎么把神经网络各层指令流水起来,在确保整网精度的同时,又有高性能。 但有时做了半天,却发现流水根本就流不起来,总是莫名其妙地被卡住。 真的是一顿…...
LeetCode刷题——动态规划(C/C++)
文章目录[简单]买股票的最佳时机[简单]爬楼梯[中等]最长递增子序列[中等]最大连续子数组和[简单]买股票的最佳时机 原题链接 题解 min:今天之前买股的最低价 res:最大利润 每一天比较今天和往前的最低价差值能否比最大利润还大 class Solution { publ…...
车载智能终端TBOX
YD886 终端设备是基于GSM/WCDMA全网通讯方式的GPS定位移动终端,车载设备具有强大的车辆监控管理、CAN总线数据采集等功能,可以满足不同用户的需求,同时具备汽车行驶记录功能扩展应用。具体功能请以终端实际情况为准! 一、移动管家 车载智能终…...
技术分担产品之忧(上):挑选有业务专家潜力的人
你好,我是王植萌,去哪儿网的高级技术总监、TC主席。从2014年起,担任一个部门的技术负责人,有8年技术总监经验、5年TC主席的经验。这节课我会从去哪儿网产研融合的经验出发,和你聊一聊怎么让技术分担产品之忧。 技术分…...
UVa 12569 Planning mobile robot on Tree (EASY Version) 树上机器人规划(简单版) BFS 二进制
题目链接:Planning mobile robot on Tree (EASY Version) 题目描述: 给定一棵树,树上有一个位置存在一个机器人,其他mmm个位置存在石头,保证初始状态一个结点最多一个物体(一个石头或者一个机器人或者为空…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
