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] <= 104nums中的每个值都 独一无二- 题目数据保证
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 简介 高质量:编写的代码能否达到正确可靠、简洁清晰的目标 各种边界条件是否考虑完备异常情况处理,稳定性保证易读易维护编程原则 简单性 消除多余的重复性,以简单清晰的逻辑编写代码不理解的代码无法修复改进可读性 代码是写给人看的,并不是机器编写可维护代码的第一…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
