LC记录一:寻找旋转数组最小值、判断旋转数组是否存在给定元素
文章目录
- 33.搜索旋转排序数组
- 81.搜索旋转排序数组||
- 153.寻找旋转排序数组中的最小值
- 154.寻找旋转排序数组中的最小值||
- 参考链接
33.搜索旋转排序数组
https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
下面这张图片是LC154题官方题解提供的一个图片:我转载一下:
上图与本题唯一的区别是:本题题目约束数组中不包含重复元素,所以在某次旋转后,数组一定会被分为「左数组」和「右数组」
其中「左数组」和「右数组」分别单调递增。有一种特殊情况需要注意:
当数组旋转数组长度个单位后,仍然是元素组,此时这个数组也被称为「右数组」,你可能要问为什么要将其称为「右数组」而不是「左数组」,可以使用123三个元素依次旋转就能够观察到,最后一定是「右数组」同时右数组在本题以及后面的题目中,都会作为划分左右数组边界的关键所在。
第一题实现思路:
- 采用二分法,计算出mid都应的值:num[mid]
- 如果num[mid] == target,则直接返回。
- 如果不相等,则需要判断,nums[mid] 和 target的大小关系。此时就涉及到 target 和 nums[mid] 分别位于左边界还是右边界的问题。
- 我划分的标准是使用 target 和 nums[r] 对比,如果 target > nums[r] 则此时 target 一定位于左边界,如果 target < nums[r] 则此时 target一定位于右边界。在本题中由于不包含重复元素,所以不存在target == nums[r] 的情况,下面一题是这种情况。
- 当 target 划分好左边边界后,需要使用 nums[mid] 和 nums[r] 的大小关系判断出 mid 位于左右边界的情况,对于左右边界的值分别进行比较。
- target 位于左边界时,mid 位于右边界:r = mid - 1。
- target 位于左边界时,mid 位于左边界:target > nums[mid] 时,l = mid + 1;target < nums[mid] 时,r = mid - 1;两者相等的情况上面已经判断过了
- target 位于右边界时,mid 位于左边界:l = mid + 1。
- target 位于右边界时,mid 位于右边界:target > nums[mid] 时,l = mid + 1;target < nums[mid] 时,r = mid - 1;
具体代码如下:
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] == target){return mid;}if(target > nums[r]){// target位于左边界if(nums[mid] < nums[r]){// mid位于右边界r = mid - 1;}else{// mid位于左边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}else{// target位于右边界if(nums[mid] > nums[r]){// mid位于左边界l = mid + 1;}else{// mid位于右边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}}System.out.println(l);return nums[l] == target ? l : -1;}
}
81.搜索旋转排序数组||
https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/
此题就是对上面题目的扩展,上一题目中判断是否位于左边界,直接和nums[r] 相比,大于则位于左边界,随后直接位于右边界,根本不考虑相等的情况,因为第一题元素值不相等,根本不存在 == nums[r] 这中情况。
本题存在相等元素,只需要在上一题的判断的基础上,添加上是否 等于 nums[r] 这种情况即可。
具体见代码及注释:
class Solution {public boolean search(int[] nums, int target) {int l = 0, r = nums.length - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] == target){return true;}if(target > nums[r]){// 此时target位于左边界数组if(nums[mid] == nums[r]){// mid不确定位于左边界,还是右边界,此时只能缩小右边界的范围r = r - 1;}else if(nums[mid] < nums[r]){// mid位于右边界r = mid - 1;}else{// mid位于左边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}else if(target < nums[r]){// 此时target位于右边界数组if(nums[mid] == nums[r]){// mid不确定位于左边界,还是右边界,此时只能缩小右边界的范围r = r - 1;}else if(nums[mid] > nums[r]){// mid位于左边界l = mid + 1;}else{// mid位于右边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}else if(target == nums[r]){// target直接和右边界相等,则直接返回return true;}}return nums[l] == target;}
}
153.寻找旋转排序数组中的最小值
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
这道题目寻找旋转数组的最小值,就是旋转数组的左右边界交界处。
仍然可以利用二分取得mid后和nums[r] 进行比较。
- nums[mid] > nums[r] : 此时mid位于左边界,肯定不符合要求,直接 l = mid + 1;
- nums[mid] < nums[r] : 此时mid位于右边界,由于二分查找计算的mid是向下取整的,所以 l <= mid < r ;所以此时直接令 r = mid 即可,不需要额外mid - 1。
代码展示:
class Solution {public int findMin(int[] nums) {int l = 0, r = nums.length - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] > nums[r]){// 此时mid位于左边界l = mid + 1;}else{// 此时mid位于右边界,由于向下取整,直接 mid = r 主要考虑到r可能此时就是右边界函数的最左边小值r = mid;}}return nums[l];}
}
154.寻找旋转排序数组中的最小值||
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/
如果对与1题到2题的演化关系比较熟练了,那么此时从3题演化到4题,也可以类比,在3题的基础上添加nums[mid] == num[r] 相等条件的判断即可。
代码演示:
class Solution {public int findMin(int[] nums) {int len = nums.length;int l = 0, r = len - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] > nums[r]){// 此时m位于左排序数组中l = mid + 1;}else if(nums[mid] < nums[r]){// 此时m位于右排序数组中r = mid;}else{r = r - 1;}}return nums[l];}
}
对于第四题可以参考下述链接加深理解。
参考链接
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/
相关文章:

LC记录一:寻找旋转数组最小值、判断旋转数组是否存在给定元素
文章目录 33.搜索旋转排序数组81.搜索旋转排序数组||153.寻找旋转排序数组中的最小值154.寻找旋转排序数组中的最小值||参考链接 33.搜索旋转排序数组 https://leetcode.cn/problems/search-in-rotated-sorted-array/description/ 下面这张图片是LC154题官方题解提供的一个图…...

关于 JVM 个人 NOTE
目录 1、JVM 的体系结构 2、双亲委派机制 3、堆内存调优 4、关于GC垃圾回收机制 4.1 GC中的复制算法 4.2 GC中的标记清除算法 1、JVM 的体系结构 "堆"中存在垃圾而"栈"中不存在垃圾的原因: 堆(Heap) 用途ÿ…...
网络工程和信息安全专业应该考哪些证书?
网络工程和信息安全专业在校大学生可以考的网络信息安全方向证书有NISP一级、NISP二级、CISP-DSG、CISP-PTE! 一、NISP一级 NISP一级是网络安全行业入门证书! NISP一级报名条件:年满16周岁即可 NISP一级报名时间:随时可报 NI…...

ASP.NET Core 创建使用异步队列
示例图 在 ASP.NET Core 应用程序中,执行耗时任务而不阻塞线程的一种有效方法是使用异步队列。在本文中,我们将探讨如何使用 .NET Core 和 C# 创建队列结构以及如何使用此队列异步执行操作。 步骤 1:创建 EmailMessage 类 首先,…...

从Linux系统的角度看待文件-基础IO
目录 从Linux系统的角度看待文件 系统文件I/O open write read 文件操作的本质 vim中批量注释的方法 从Linux系统的角度看待文件 关于文件的共识: 1.空文件也要占用磁盘空间 2.文件内容属性 3.文件操作包括文件内容/文件属性/文件内容属性 4.文件路径文…...

总结之Coze 是一站式 AI Bot 开发平台——工作流使用及coze总结(三)
工作流介绍 工作流支持通过可视化的方式,对插件、大语言模型、代码块等功能进行组合,从而实现复杂、稳定的业务流程编排,例如旅行规划、报告分析等。 当目标任务场景包含较多的步骤,且对输出结果的准确性、格式有严格要求时&…...

汽车线束之故障诊断方案-TDR测试
当前,在汽车布局中的线束的性能要求越来越高。无法通过简单的通断测试就能满足性能传输要求。早起对智能化要求不高,比如没有激动雷达、高清摄像、中央CPU等。 近几年的智能驾驶对网络传输要求越来越高,不但是高速率,还需要高稳定…...

自己做个国庆75周年头像生成器
版权声明:本文为博主原创文章,转载请在显著位置标明本文出处以及作者网名,未经作者允许不得用于商业目的。 下载相关代码:【免费】《自己做个国庆75周年头像生成器》代码资源-CSDN文库 又是一年国庆节,今年使用国旗做…...

2k1000LA loongnix 安装java
问题: 客户 需要在 loongnix 上 使用 java 的程序。 情况说明: 使用 apt get 是无法 安装java 的。 按照的资料就行。 首先是 下载 loongarch64 的 java 的压缩包。这个我已经下载下来了。 社区下载地址: http://www.loongnix.cn/zh/api/…...
中信银行西安分行:构建科技金融体质 做好科技金融“大文章”
中央金融工作会议提出,要做好科技金融、绿色金融、普惠金融、养老金融、数字金融五篇大文章。做好新时代金融五篇大文章,不仅为统筹推进经济和金融高质量发展明确了重点,也锚定了着力点。 作为一家拥有红色基因的国有金融企业,中…...

Linux系统性能调优技巧详解
Linux系统性能调优技巧详解 Linux 系统广泛应用于服务器、嵌入式设备以及开发工作站中,因此对其进行性能调优是保障系统高效运行的关键之一。性能调优不仅可以提高系统的响应速度,还能有效优化资源使用,避免瓶颈。在这篇文章中,我…...
MFC工控项目实例之十九手动测试界面输出信号切换
承接专栏《MFC工控项目实例之十八手动测试界面输入信号实时检测》 根据板卡设置界面组合框选项设定的输出信号,通过读取文件中保存的键值,用单选按钮切换输出信号接通、关闭。 1、在Data_1.h文件中添加代码 CString COMB_Data_O_1[]{"夹紧",&…...

数据结构——栈的基本操作
前言 介绍 🍃数据结构专区:数据结构 参考 该部分知识参考于《数据结构(C语言版 第2版)》55 ~ 59页 🌈每一个清晨,都是世界对你说的最温柔的早安:ૢ(≧▽≦)و✨ 1、栈的基本概念 栈&#x…...

Chainlit集成LlamaIndex实现知识库高级检索(组合对象检索)
检索原理 对象组合索引的原理 是利用IndexNode索引节点,将两个不同类型的检索器作为节点对象,使用 SummaryIndex (它可以用来构建一个包含多个索引节点的索引结构。这种索引通常用于从多个不同的数据源或索引方法中汇总信息,并能…...

万界星空科技铜拉丝行业MES系统,实现智能化转型
一、铜拉丝行业生产管理的难点主要体现在以下几个方面: 1、标准严格:铜线产品对质量的要求极高,特别是在电气性能、导电性、耐腐蚀性等方面,任何微小的瑕疵都可能影响产品的使用效果和安全性。 2、过程监控:生产过程…...

ECCV 2024 现场:参会者付高价、跨万里,却无法入场?
ECCV(European Conference on Computer Vision,欧洲计算机视觉国际会议)是计算机视觉领域的重要国际会议之一,与CVPR和ICCV并称为计算机视觉的三大顶级会议。 ECCV2024是该系列会议的第18届会议,2024年9月29日至10月4…...

使用rsync+jenkins实现服务自动部署全流程
项目背景:城市政务云服务器没有上k8s,所有后端服务都是原始方式部署启动 (java -jar xxx.jar),那么有没有方式简化部署难度,实现自动部署?当然是有的,下面详细介绍(以Cen…...
python 实现decision tree决策树算法
decision tree决策树算法介绍 决策树算法(Decision Tree Algorithm)是一种基于输入特征对实例进行分类的树结构模型,主要用于分类和回归任务。其基本原理是根据训练数据的特征属性和类别标签之间的关系,生成一个能够对新样本进行…...

前端大模型入门:实战篇之Vue3+Antdv+transformers+本地模型实现增强搜索
本文将之前的文章,实现一个场景的实战应用,包含代码等内容。利用纯前端实现增强的列表搜索,抛弃字符串匹配,目标是使用番茄关键字可以搜索到西红柿 1 准备工作 1.1 了解llm和web开发 web端的ai开发参考 前端大模型入门ÿ…...

《向量数据库指南》——Fivetran 的 Partner SDK:构建自定义连接器和目标
哈哈,说到 Fivetran 的 Partner SDK,这可真是个好东西啊!作为向量数据库领域的“老司机”,我今天就来给大家详细讲讲这个 SDK 的厉害之处,以及如何用它来构建自定义连接器和目标,实现与 Fivetran 自动化数据移动平台的无缝集成。 一、Fivetran Partner SDK:开启自定义连…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...

9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...

Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...

【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...