LeetCode 33 搜索旋转排序数组
题目描述
搜索旋转排序数组
整数数组 nums
按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums
在预先未知的某个下标 k
(0 <= k < nums.length
)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7]
在下标 3
处经旋转后可能变为 [4,5,6,7,0,1,2]
。
给你 旋转后 的数组 nums
和一个整数 target
,如果 nums
中存在这个目标值 target
,则返回它的下标,否则返回 -1
。
你必须设计一个时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:
输入:nums = [1], target = 0
输出:-1
提示:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums
中的每个值都 独一无二- 题目数据保证
nums
在预先未知的某个下标上进行了旋转 -104 <= target <= 104
解法
注意旋转后数组的特点:
- 4,5,6,7(最大),0(最小),1,2
- 数组最左边的元素和最右边的元素在原来单调递增的数组中是相邻的
- 数组从左到右,先是递增,然后到原来有序数组的第一个元素即最小值后,又开始递增
- 从原来最小元素为分割点,左边的元素一定大于右边所有元素(包含最小元素)
根据以上特点,使用二分查找:
- 旋转后的数组变成两个局部有序的数组 [4,5,6,7] 和 [0,1,2]
- 每次找到mid后,先看 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的
- 并根据有序的那个部分确定我们该如何改变二分查找的上下界
- 如果中间元素 >= 第一个元素:则说明中间元素在左边第一个元素到最大元素之间
- 反之(中间元素 <= 最后一个元素):则说明中间元素在原来最小元素和现在最右边元素之间
java代码:
class Solution {public int search(int[] nums, int target) {int n = nums.length;// 如果数组长度为0,返回-1if (n == 0) {return -1;}// 如果数组长度为1,直接比较元素与targetif (n == 1) {return nums[0] == target ? 0 : -1;}// 左索引从0开始int left = 0;// 右索引从末尾n-1开始int right = n - 1;// 使用二分查找while (left <= right) {// 求中间索引值midint mid = (left + right) / 2;// 如果mid索引对应值等于target,返回midif (nums[mid] == target) {return mid;}// 如果中间索引值大于等于第一个元素,则中间元素在左边第一个元素到最大元素之间if (nums[0] <= nums[mid]) {// 如果目标值>=第一个元素 && 目标值<中间元素// 说明目标值在左元素和中间元素之间(这部分是有序的),右索引=mid-1if (nums[0] <= target && target < nums[mid]) {right = mid -1;} else {// 否则说明目标值在中间元素和最后一个元素之间,左索引=mid+1left = mid + 1;}} else { // 中间元素在原来最小元素和现在最右边元素之间// 如果目标值<=最后一个元素 && 目标值>中间元素// 说明目标值在中间元素和最后一个元素之间(这部分是有序的),左索引=mid+1if (nums[n-1] >= target && target > nums[mid]) {left = mid + 1;} else {// 否则说明目标值在中间元素和最后一个元素之间,左索引=mid+1right = mid -1;}}}return -1;}
}
复杂度
- 时间复杂度:
O(log(n))
,其中 n 是数组长度 - 空间复杂度:
O(1)
相关文章:
LeetCode 33 搜索旋转排序数组
题目描述 搜索旋转排序数组 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], ..., num…...

分类预测 | Python实现基于SVM-RFE-LSTM的特征选择算法结合LSTM神经网络的多输入单输出分类预测
分类预测 | Python实现基于SVM-RFE-LSTM的特征选择算法结合LSTM神经网络的多输入单输出分类预测 目录 分类预测 | Python实现基于SVM-RFE-LSTM的特征选择算法结合LSTM神经网络的多输入单输出分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 基于SVM-RFE-LSTM的特征…...

JetBrains Rider使用总结
简介: JetBrains Rider 诞生于2016年,一款适配于游戏开发人员,是JetBrains旗下一款非常年轻的跨平台 .NET IDE。目前支持包括.NET 桌面应用、服务和库、Unity 和 Unreal Engine 游戏、Xamarin 、ASP.NET 和 ASP.NET Core web 等多种应用程序…...

C# Emgu.CV4.8.0读取rtsp流录制mp4可分段保存
【官方框架地址】 https://github.com/emgucv/emgucv 【算法介绍】 EMGU CV(Emgu Computer Vision)是一个开源的、基于.NET框架的计算机视觉库,它提供了对OpenCV(开源计算机视觉库)的封装。EMGU CV使得在.NET应用程序…...

java碳排放数据信息管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目
一、源码特点 java Web碳排放数据信息管理系统是一套完善的java web信息管理系统,对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。开发环 境为TOMCAT7.0,Myeclipse8.5开发,数据库为…...

K8S陈述式资源管理(1)
命令行: kubectl命令行工具 优点: 90%以上的场景都可以满足对资源的增,删,查比较方便,对改不是很友好 缺点:命令比较冗长,复杂,难记声明式 声明式:K8S当中的yaml文件来实现资源管理 GUI:图形…...

STL map容器与pair类模板(解决扫雷问题)
CSTL之Map容器 - 数据结构教程 - C语言网 (dotcpp.com)https://www.dotcpp.com/course/118CSTL之Pair类模板 - 数据结构教程 - C语言网 (dotcpp.com)https://www.dotcpp.com/course/119 刷到一个扫雷的题目,之前没有玩怎么过扫雷,于是我就去玩了玩…...

【React系列】Portals、Fragment
本文来自#React系列教程:https://mp.weixin.qq.com/mp/appmsgalbum?__bizMzg5MDAzNzkwNA&actiongetalbum&album_id1566025152667107329) Portals 某些情况下,我们希望渲染的内容独立于父组件,甚至是独立于当前挂载到的DOM元素中&am…...

ByteTrack算法流程的简单示例
ByteTrack ByteTrack算法是将t帧检测出来的检测框集合 D t {\mathcal{D}_{t}} Dt 和t-1帧预测轨迹集合 T ~ t − 1 {\tilde{T}_{t-1}} T~t−1 进行匹配关联得到t帧的轨迹集合 T t {T_{t}} Tt。 首先使用检测器检测t帧的图像得到检测框集合 D t {\mathcal{D}_{t}} …...

免费的GPT4来了,你还不知道吗?
程序员的公众号:源1024,获取更多资料,无加密无套路! 最近整理了一波电子书籍资料,包含《Effective Java中文版 第2版》《深入JAVA虚拟机》,《重构改善既有代码设计》,《MySQL高性能-第3版》&…...

win10报错“zlib.dll文件丢失,软件无法启动”,修复方法,亲测有效
zlib.dll文件是一个由Zlib创建的动态链接库文件,它是用于Windows操作系统的数据压缩和解压缩的软件。Zlib是一个广泛使用的软件库,广泛应用在许多不同类型的软件中,包括游戏、浏览器和操作系统。 zlib.dll的主要作用是提供数据压缩和解压缩的…...
MFC中如何使用CListCtrl可以编辑,并添加鼠标右键及双击事件。
要在MFC中使用CListCtrl来实现编辑功能,可以按照以下步骤进行操作: 在对话框资源中添加CListCtrl控件,并设置合适的属性。在对话框类的头文件中添加成员变量来管理CListCtrl控件,例如: CListCtrl m_listCtrl; 3. 在O…...

[每周一更]-(第81期):PS抠图流程(扭扭曲曲的身份证修正)
应朋友之急,整理下思路,分享一下~~ 分两步走:先用磁性套索工具圈出要处理的图;然后使用透视剪裁工具,将扭曲的图片拉平即可;(macbook pro) 做事有规则,才能更高效;用什么工具,先列举…...

Kafka安全认证机制详解之SASL_PLAIN
一、概述 官方文档: https://kafka.apache.org/documentation/#security 在官方文档中,kafka有五种加密认证方式,分别如下: SSL:用于测试环境SASL/GSSAPI (Kerberos) :使用kerberos认证,密码是…...

2023南京理工大学通信工程818信号系统及数电考试大纲
注:(Δ)表示重点内容。具体内容详见博睿泽信息通信考研论坛 参考书目: [1] 钱玲,谷亚林,王海青. 信号与系统(第五版). 北京:电子工业出版社 [2] 郑君里,应…...

wsl(ubuntu)创建用户
我们打卡ubuntu窗口,如果没有创建用户,那么默认是root用户 用户的增删改查 查 查询所有的用户列表 cat /etc/passwd | cut -d: -f1cat /etc/passwd: 这个命令用于显示 /etc/passwd 文件的内容。/etc/passwd 文件包含了系统上所有用户的基本信息。每一…...

[足式机器人]Part2 Dr. CAN学习笔记-自动控制原理Ch1-8Lag Compensator滞后补偿器
本文仅供学习使用 本文参考: B站:DR_CAN Dr. CAN学习笔记-自动控制原理Ch1-8Lag Compensator滞后补偿器 从稳态误差入手(steady state Error) 误差 Error : E ( s ) R ( s ) − X ( s ) R ( s ) − E ( s ) ⋅ K G …...

swift-碰到的问题
如何让工程不使用storyboard和scene 删除info.plist里面的Application Scene mainifest 删除SceneDelegate.swift 删除AppDelegate.swift里面的这两个方法 func application(_ application: UIApplication, configurationForConnecting connectingSceneSession: UISceneSession…...

安全与认证Week4
目录 目录 Web Security (TLS/SSL) 各层安全协议 Transport Layer Security (TLS)传输层安全性(TLS) SSL和TLS的联系与区别 TLS connection&session 连接与会话 题目2答案点 TLS ArchitectureTLS架构(5个协议) 题目1答案点 Handshake Proto…...
Golang高质量编程与性能调优实战
1.1 简介 高质量:编写的代码能否达到正确可靠、简洁清晰的目标 各种边界条件是否考虑完备异常情况处理,稳定性保证易读易维护编程原则 简单性 消除多余的重复性,以简单清晰的逻辑编写代码不理解的代码无法修复改进可读性 代码是写给人看的,并不是机器编写可维护代码的第一…...

超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...

Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...

群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...