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:开启自定义连…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...

label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...