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 简介 高质量:编写的代码能否达到正确可靠、简洁清晰的目标 各种边界条件是否考虑完备异常情况处理,稳定性保证易读易维护编程原则 简单性 消除多余的重复性,以简单清晰的逻辑编写代码不理解的代码无法修复改进可读性 代码是写给人看的,并不是机器编写可维护代码的第一…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
ZYNQ学习记录FPGA(一)ZYNQ简介
一、知识准备 1.一些术语,缩写和概念: 1)ZYNQ全称:ZYNQ7000 All Pgrammable SoC 2)SoC:system on chips(片上系统),对比集成电路的SoB(system on board) 3)ARM:处理器…...
