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

(二分查找)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&#xff0c;找到峰值元素并返回其索引。数组可能包含多个峰值…...

spring boot 配合element ui vue实现表格的批量删除(前后端详细教学,简单易懂,有手就行)

目录 一.前言&#xff1a; 二. 前端代码&#xff1a; 2.1.element ui组件代码 2.2删除按钮 2.3.data 2.4.methods 三.后端代码&#xff1a; 一.前言&#xff1a; 研究了其他人的博客&#xff0c;找到了一篇有含金量的&#xff0c;进行了部分改写实现前后端分离&#xff0…...

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 什么是深度学习&#xff1f; 简单来说&#xff0c;深度学习就是一种包括多个隐含层 (越多即为越深)的多层感知机。它通过组合低层特征&#xff0c;形成更为抽象的高层表示&#xff0c;用以描述被识别对象的高级属性类别或特征。 能自生成数据的中…...

在 WIndows 下安装 Apache Tinkerpop (Gremlin)

一、安装 JDK 首先安装 Java JDK&#xff0c;这个去官网下载即可&#xff0c;我下载安装的 JDK19&#xff08;jdk-19_windows-x64_bin.msi&#xff09;&#xff0c;细节不赘述。 二、去 Tinkerpop 网站下载 Gremlin 网址&#xff1a;https://tinkerpop.apache.org/ 点击下面…...

从软件的角度看待PCI和PCIE(一)

1.最容易访问的设备是什么&#xff1f; 是内存&#xff01; 要读写内存&#xff0c;知道它的地址就可以了&#xff0c;不需要什么驱动程序&#xff1b; volatile unsigned int *p 0xffff8811; unsigned int val; *p val; val *p;只有内存能这样简单、方便的使用吗&#xf…...

DSP_TMS320F28377D_ADC学习笔记

前言 DSP各种模块的使用&#xff0c;基本上就是 GPIO复用配置、相关控制寄存器的配置、中断的配置。本文主要记录本人对ADC模块的学习笔记。TMS320F28377D上面有24路ADC专用IO&#xff0c;这意味着不需要进行GPIO复用配置。 只需要考虑相关控制寄存器和中断的配置。看代码请直…...

springcloud3 Nacos中namespace和group,dataId的联系

一 Namespance和group和dataId的联系 1.1 3者之间的联系 话不多说&#xff0c;上答案&#xff0c;如下图&#xff1a; namespance用于区分部署环境&#xff0c;group和dataId用于逻辑上区分两个目标对象。 二 案例&#xff1a;实现读取注册中心的不同环境下的配置文件 …...

[YOLO] yolo理解博客笔记

YOLO v2和V3 关于设置生成anchorbox&#xff0c;Boundingbox边框回归的过程详细解读 YOLO v2和V3 关于设置生成anchorbox&#xff0c;Boundingbox边框回归的个人理解https://blog.csdn.net/shenkunchang1877/article/details/105648111YOLO v1网络结构计算 Yolov1-pytorch版 …...

清华源pip安装Python第三方包

一、更换PIP源PIP源在国外&#xff0c;速度慢&#xff0c;可以更换为国内源&#xff0c;以下是国内一些常用的PIP源。豆瓣(douban) http://pypi.douban.com/simple/ (推荐)清华大学 https://pypi.tuna.tsinghua.edu.cn/simple/阿里云 http://mirrors.aliyun.com/pypi/simple/中…...

python线程池【ThreadPoolExecutor()】批量获取博客园标题数据

转载&#xff1a;蚂蚁学python 网址&#xff1a;【【2021最新版】Python 并发编程实战&#xff0c;用多线程、多进程、多协程加速程序运行】 https://www.bilibili.com/video/BV1bK411A7tV/?p8&share_sourcecopy_web&vd_sourced0ef3d08fdeef1740bab49cdb3e96467实战案…...

LearnOpenGL-入门-8.坐标系统

本人刚学OpenGL不久且自学&#xff0c;文中定有代码、术语等错误&#xff0c;欢迎指正 我写的项目地址&#xff1a;https://github.com/liujianjie/LearnOpenGLProject LearnOpenGL中文官网&#xff1a;https://learnopengl-cn.github.io/ 文章目录坐标系统概述局部空间世界空…...

windows10使用wsl2安装docker

配环境很麻烦&#xff0c;想利用docker的镜像环境跑一下代码整个安装过程的原理是&#xff1a;windows使用docker&#xff0c;必须先安装一个linux虚拟机&#xff0c;才可运行docker&#xff0c;而采用wsl2安装虚拟机是目前最好的方法第一步 windows安装wsl2控制面板->程序-…...

Javascript的API基本内容(六)

一、正则表达式 1.定义规则 const reg /表达式/ 其中/ /是正则表达式字面量正则表达式也是对象 2.使用正则 test()方法 用来查看正则表达式与指定的字符串是否匹配如果正则表达式与指定的字符串匹配 &#xff0c;返回true&#xff0c;否则false 3.元字符 比如&#xff0…...

电压放大器和电流放大器的区别是什么意思

在日常电子实验测试中&#xff0c;很多电子工程师都会使用到电压放大器和电流放大器&#xff0c;但是很多新手工程师却无法区分两者的区别&#xff0c;下面就让安泰电子来为我们讲解电压放大器和电流放大器的区别是什么意思。 一、电压放大器介绍&#xff1a; 电压放大器是一种…...

cast提前!最简单有效的神经网络优化方法,没有之一!

做优化有时候真的很头疼&#xff0c;绞尽脑汁的想怎么做算法等价&#xff0c;怎么把神经网络各层指令流水起来&#xff0c;在确保整网精度的同时&#xff0c;又有高性能。 但有时做了半天&#xff0c;却发现流水根本就流不起来&#xff0c;总是莫名其妙地被卡住。 真的是一顿…...

LeetCode刷题——动态规划(C/C++)

文章目录[简单]买股票的最佳时机[简单]爬楼梯[中等]最长递增子序列[中等]最大连续子数组和[简单]买股票的最佳时机 原题链接 题解 min&#xff1a;今天之前买股的最低价 res&#xff1a;最大利润 每一天比较今天和往前的最低价差值能否比最大利润还大 class Solution { publ…...

车载智能终端TBOX

YD886 终端设备是基于GSM/WCDMA全网通讯方式的GPS定位移动终端,车载设备具有强大的车辆监控管理、CAN总线数据采集等功能&#xff0c;可以满足不同用户的需求&#xff0c;同时具备汽车行驶记录功能扩展应用。具体功能请以终端实际情况为准&#xff01; 一、移动管家 车载智能终…...

技术分担产品之忧(上):挑选有业务专家潜力的人

你好&#xff0c;我是王植萌&#xff0c;去哪儿网的高级技术总监、TC主席。从2014年起&#xff0c;担任一个部门的技术负责人&#xff0c;有8年技术总监经验、5年TC主席的经验。这节课我会从去哪儿网产研融合的经验出发&#xff0c;和你聊一聊怎么让技术分担产品之忧。 技术分…...

UVa 12569 Planning mobile robot on Tree (EASY Version) 树上机器人规划(简单版) BFS 二进制

题目链接&#xff1a;Planning mobile robot on Tree (EASY Version) 题目描述&#xff1a; 给定一棵树&#xff0c;树上有一个位置存在一个机器人&#xff0c;其他mmm个位置存在石头&#xff0c;保证初始状态一个结点最多一个物体&#xff08;一个石头或者一个机器人或者为空…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

相关类相关的可视化图像总结

目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系&#xff0c;可直观判断线性相关、非线性相关或无相关关系&#xff0c;点的分布密…...

Java后端检查空条件查询

通过抛出运行异常&#xff1a;throw new RuntimeException("请输入查询条件&#xff01;");BranchWarehouseServiceImpl.java // 查询试剂交易&#xff08;入库/出库&#xff09;记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...

ThreadLocal 源码

ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物&#xff0c;因为每个访问一个线程局部变量的线程&#xff08;通过其 get 或 set 方法&#xff09;都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段&#xff0c;这些类希望将…...

大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程

基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...

react更新页面数据,操作页面,双向数据绑定

// 路由不是组件的直接跳转use client&#xff0c;useEffect&#xff0c;useRouter&#xff0c;需3个结合&#xff0c; use client表示客户端 use client; import { Button,Card, Space,Tag,Table,message,Input } from antd; import { useEffect,useState } from react; impor…...

【threejs】每天一个小案例讲解:创建基本的3D场景

代码仓 GitHub - TiffanyHoo/three_practices: Learning three.js together! 可自行clone&#xff0c;无需安装依赖&#xff0c;直接liver-server运行/直接打开chapter01中的html文件 运行效果图 知识要点 核心三要素 场景&#xff08;Scene&#xff09; 使用 THREE.Scene(…...

JUC并发编程(二)Monitor/自旋/轻量级/锁膨胀/wait/notify/锁消除

目录 一 基础 1 概念 2 卖票问题 3 转账问题 二 锁机制与优化策略 0 Monitor 1 轻量级锁 2 锁膨胀 3 自旋 4 偏向锁 5 锁消除 6 wait /notify 7 sleep与wait的对比 8 join原理 一 基础 1 概念 临界区 一段代码块内如果存在对共享资源的多线程读写操作&#xf…...