当前位置: 首页 > 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;一个石头或者一个机器人或者为空…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

JavaScript 数据类型详解

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

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

Python 高效图像帧提取与视频编码:实战指南

Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...