当前位置: 首页 > 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. 课前小问…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...