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

【Leetcode每日一题】二分查找 - 寻找旋转排序数组中的最小值(难度⭐⭐)(22)

1. 题目解析

Leetcode链接:153. 寻找旋转排序数组中的最小值

这个题目乍一看很长很复杂,又是旋转数组又是最小值的

但是仔细想想,结合题目给的示例,不难看出可以用二分的方法来解决

核心在于找到给定数组里面的最小值


2. 算法原理

题目规定的数组规则如下图所示:

我们的目标是找到一个特定的点C。

从给定的图像中,我们观察到在区间[A,B]内的所有点的值都严格大于D点的值,而C点的值则严格小于D点的值。但需要注意的是,当区间[C,D]只包含一个元素时,C点的值有可能等于D点的值。

因此,我们初始化两个指针,left和right,分别代表搜索区间的左右边界。接着,根据中间点mid的值与D点值的比较结果,我们可以确定下一次搜索的区间:

  • 如果mid位于[A,B]区间内,即mid的值严格大于D点的值,那么下一次搜索区间将缩小为[mid + 1,right]。
  • 如果mid位于[C,D]区间内,即mid的值小于或等于D点的值,那么下一次搜索区间将缩小为[left,mid]。

当搜索区间的长度缩减为1时,我们就找到了所需的点C。


3. 代码编写

class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size() - 1;int left = 0, right = n, mid = 0;while(left < right){mid = (left + right)/2;if(nums[mid] > nums[n]){left = mid + 1;}else if(nums[mid] <= nums[n]){right = mid;}}return nums[left];}
};

The Last

嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。

觉得有点收获的话,不妨给我点个吧!

如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~

相关文章:

【Leetcode每日一题】二分查找 - 寻找旋转排序数组中的最小值(难度⭐⭐)(22)

1. 题目解析 Leetcode链接&#xff1a;153. 寻找旋转排序数组中的最小值 这个题目乍一看很长很复杂&#xff0c;又是旋转数组又是最小值的 但是仔细想想&#xff0c;结合题目给的示例&#xff0c;不难看出可以用二分的方法来解决 核心在于找到给定数组里面的最小值 2. 算法原…...

QT C++实战:实现用户登录页面及多个界面跳转

主要思路 一个登录界面&#xff0c;以管理员Or普通用户登录管理员&#xff1a;一个管理员的操作界面&#xff0c;可以把数据录入到数据库中。有返回登陆按钮&#xff0c;可以选择重新登陆&#xff08;管理员Or普通用户普通用户&#xff1a;一个主界面&#xff0c;负责展示视频…...

我的世界游戏服务器平台推荐哪里找?

我的世界服务器可以在多个平台上租赁&#xff0c;以下是一些推荐的游戏服务器平台。 1.玩家可以通过互联网上的一些平台租用游戏服务器。其中&#xff0c;国内大厂平台有阿里云、腾讯云、华为云等。这些平台提供了丰富的服务器配置和带宽选择&#xff0c;玩家可以根据自己的需求…...

用于制作耳机壳的倒模专用UV树脂有什么特点?

制作耳机壳的UV树脂耳机壳UV胶具有以下特点&#xff1a; 快速固化&#xff1a;UV树脂可以在紫外线的照射下迅速固化&#xff0c;大大缩短了制作时间。高硬度与高耐磨性&#xff1a;UV树脂具有较高的硬度和耐磨性&#xff0c;能够提供良好的保护效果。透明度高&#xff1a;UV树…...

将c、c++变为python

1.编写cpp文件 #include "pycpp.h" #include <iostream>using namespace std;PyCpp::PyCpp(){}void PyCpp::sayHello(int a){cout << "Hello Python, I am C."<<a << endl; }2.编写头文件&#xff08;声明变量&#xff09; clas…...

golang学习7,glang的web的restful接口结构体传参

接口&#xff1a; //POST请求 返回json 接口传参json r.POST("/postJson", controller.PostUserInfo) 1.定义结构体 //定义结构体 type Search struct {Id intName string }2.结构体传参 //结构体传参 func PostUserInfo(c *gin.Context) {search : &Searc…...

python模型训练

目录 1、新建模型 train_model.py 2、运行模型 &#xff08;1&#xff09;首先会下载data文件库 &#xff08;2&#xff09;完成之后会开始训练模型&#xff08;10次&#xff09; 3、 训练好之后&#xff0c;进入命令集 4、输入命令&#xff1a;python -m tensorboard.ma…...

逆向案例三:动态xhr包中AES解密的一般步骤,以精灵数据为例

补充知识&#xff1a;进行AES解密需要知道四个关键字&#xff0c;即密钥key,向量iv,模式mode,填充方式pad 一般网页AES都是16位的&#xff0c;m3u8视频加密一般是AES-128格式 网页链接:https://www.jinglingshuju.com/articles 进行抓包结果返回的是密文&#xff1a; 一般思…...

超越CPU和GPU:引领AI进化的LPU

什么是CPU CPU&#xff08;Central Processing Unit&#xff09;是由数十亿个晶体管构成的&#xff0c;可以拥有多个处理核心&#xff0c;通常被称为计算机的“大脑”。它对所有现代计算系统至关重要&#xff0c;因为它执行计算机和操作系统所需的命令和进程。CPU在决定程序运…...

MySQL 逗号分隔查询--find_in_set()函数

业务场景&#xff1a; 在使用MySQL的时候&#xff0c;可能的某个字段存储的是一个英文逗号分割的字符串&#xff08;这里我们不讨论表设计的合理性&#xff09;&#xff0c;如图所示&#xff1a; 我们在查询的时候需要匹配逗号分割中的某个字符串&#xff0c;该怎么查询呢&am…...

【物联网应用案例】智能农业的 9 个技术用例

一、农业中的物联网用例 一般而言&#xff0c;农业物联网传感器以及农业物联网应用有多种类型&#xff1a; 1. 气候条件监测 气象站无疑是当今智能农业领域最受欢迎的设备。这款设备集成了多种智能农业传感器&#xff0c;能够在现场对各类数据进行收集&#xff0c;然后迅速将…...

前端开发——ElementUI组件的使用

文章目录 1. Tabs标签页2. 单选框 el-radio3. 复选框 el-checkbox4. 下拉框 el-select5. 表格 el-table6. 对话框 el-dialog7. 文字提示 el-tooltip8. 抽屉 el-drawer 1. Tabs标签页 <template><el-tabs v-model"activeName" tab-click"handleClick&q…...

Unity编写Shader内置各种矩阵和方法介绍

嗨&#xff0c;各位小伙伴们&#xff0c;我是你们的好朋友咕噜铁蛋&#xff01;今天&#xff0c;我们要来聊一聊关于Unity中编写Shader时内置的各种矩阵和方法。作为Unity开发者&#xff0c;掌握Shader编写是非常重要的一项技能&#xff0c;而了解内置的矩阵和方法将帮助我们更…...

初学者如何使用QT新建一个包含UI界面的C++项目

文章目录 一、下载并安装QT51、下载安装包2、注册/登录账号3、安装qt6 二、新建QT Widget项目1、新建项目并且运行2、易错点&#xff1a;可能运行成功得到UI界面但是会报错&#xff08;原因是使用了中文路径&#xff09; 一、下载并安装QT5 1、下载安装包 进入下载网址 Windo…...

韦东山嵌入式Liunx入门驱动开发四

文章目录 一、异常与中断的概念及处理流程1-1 中断的引入1-2 栈(1) CPU实现a ab的过程(2) 进程与线程 1-3 Linux系统对中断处理的演进1-4 Linux 中断系统中的重要数据结构(1) irq_desc 结构体(2) irqaction 结构体(3) irq_data 结构体(4) irq_domain 结构体(5) irq_domain 结构…...

ubuntu基础操作(1)-个人笔记

搜狗输入法Linux官网-首页搜狗输入法for linux—支持全拼、简拼、模糊音、云输入、皮肤、中英混输https://pinyin.sogou.com/linux 1.关闭sudo密码&#xff1a; 终端&#xff08;ctrl alt t&#xff09;输入 sudo visudo 打开visudo 找到 %sudo ALL(ALL:ALL) ALL 这一行…...

Spring Cloud2022之OpenFeign使用以及部分源码分析

OpenFeign使用 Feign和OpenFeign Feign是Netflix开发的⼀个轻量级RESTful的HTTP服务客户端&#xff0c;可以使用⽤它来发起请求&#xff0c;进行远程调用。Fegin是以Java接口注解的⽅式调⽤Http请求&#xff0c;而不是像RestTemplate那样&#xff0c;在Java中通过封装HTTP请求…...

【非比较排序】计算排序算法

目录 CountSort计数排序 整体思想 图解分析 代码实现 时间复杂度&优缺分析 CountSort计数排序 计数排序是一种非比较排序&#xff0c;不需要像前面的排序一样去比较。 计数排序的特性总结&#xff1a; 1. 计数排序在数据范围集中时&#xff0c;效率很高&#xff0c;但…...

数据结构与算法 - 数组与二分查找 + Leetcode典型题

1. 什么是数组 数组是存放在连续内存空间上的相同类型数据的集合。 数组可以方便的通过下标索引的方式获取到下标下对应的数据。 C中二维数组在地址空间上也是连续的。 需注意&#xff1a; 数组的下标从0开始。数组内存空间的地址是连续的。数组的元素是不能删的&#xff0c…...

SQL进阶(三):Join 小技巧:提升数据的处理速度

复杂数据结构处理&#xff1a;Join 小技巧&#xff1a;提升数据的处理速度 本文是在原本sql闯关的基础上总结得来&#xff0c;加入了自己的理解以及疑问解答&#xff08;by GPT4&#xff09; 原活动链接 用到的数据&#xff1a;链接 提取码&#xff1a;l03e 目录 1. 课前小问…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...