当前位置: 首页 > news >正文

LeetCode 33 搜索旋转排序数组

题目描述

搜索旋转排序数组

整数数组 nums 按升序排列,数组中的值 互不相同

在传递给函数之前,nums 在预先未知的某个下标 k0 <= 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] 哪个部分是有序的
  • 并根据有序的那个部分确定我们该如何改变二分查找的上下界
    1. 如果中间元素 >= 第一个元素:则说明中间元素在左边第一个元素到最大元素之间
    2. 反之(中间元素 <= 最后一个元素):则说明中间元素在原来最小元素和现在最右边元素之间

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 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [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使用总结

简介&#xff1a; JetBrains Rider 诞生于2016年&#xff0c;一款适配于游戏开发人员&#xff0c;是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&#xff08;Emgu Computer Vision&#xff09;是一个开源的、基于.NET框架的计算机视觉库&#xff0c;它提供了对OpenCV&#xff08;开源计算机视觉库&#xff09;的封装。EMGU CV使得在.NET应用程序…...

java碳排放数据信息管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

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

K8S陈述式资源管理(1)

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

STL map容器与pair类模板(解决扫雷问题)

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

【React系列】Portals、Fragment

本文来自#React系列教程&#xff1a;https://mp.weixin.qq.com/mp/appmsgalbum?__bizMzg5MDAzNzkwNA&actiongetalbum&album_id1566025152667107329) Portals 某些情况下&#xff0c;我们希望渲染的内容独立于父组件&#xff0c;甚至是独立于当前挂载到的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来了,你还不知道吗?

程序员的公众号&#xff1a;源1024&#xff0c;获取更多资料&#xff0c;无加密无套路&#xff01; 最近整理了一波电子书籍资料&#xff0c;包含《Effective Java中文版 第2版》《深入JAVA虚拟机》&#xff0c;《重构改善既有代码设计》&#xff0c;《MySQL高性能-第3版》&…...

win10报错“zlib.dll文件丢失,软件无法启动”,修复方法,亲测有效

zlib.dll文件是一个由Zlib创建的动态链接库文件&#xff0c;它是用于Windows操作系统的数据压缩和解压缩的软件。Zlib是一个广泛使用的软件库&#xff0c;广泛应用在许多不同类型的软件中&#xff0c;包括游戏、浏览器和操作系统。 zlib.dll的主要作用是提供数据压缩和解压缩的…...

MFC中如何使用CListCtrl可以编辑,并添加鼠标右键及双击事件。

要在MFC中使用CListCtrl来实现编辑功能&#xff0c;可以按照以下步骤进行操作&#xff1a; 在对话框资源中添加CListCtrl控件&#xff0c;并设置合适的属性。在对话框类的头文件中添加成员变量来管理CListCtrl控件&#xff0c;例如&#xff1a; CListCtrl m_listCtrl; 3. 在O…...

[每周一更]-(第81期):PS抠图流程(扭扭曲曲的身份证修正)

应朋友之急&#xff0c;整理下思路&#xff0c;分享一下~~ 分两步走&#xff1a;先用磁性套索工具圈出要处理的图&#xff1b;然后使用透视剪裁工具&#xff0c;将扭曲的图片拉平即可&#xff1b;(macbook pro) 做事有规则&#xff0c;才能更高效;用什么工具&#xff0c;先列举…...

Kafka安全认证机制详解之SASL_PLAIN

一、概述 官方文档&#xff1a; https://kafka.apache.org/documentation/#security 在官方文档中&#xff0c;kafka有五种加密认证方式&#xff0c;分别如下&#xff1a; SSL&#xff1a;用于测试环境SASL/GSSAPI (Kerberos) &#xff1a;使用kerberos认证&#xff0c;密码是…...

2023南京理工大学通信工程818信号系统及数电考试大纲

注&#xff1a;&#xff08;Δ&#xff09;表示重点内容。具体内容详见博睿泽信息通信考研论坛 参考书目&#xff1a; [1] 钱玲&#xff0c;谷亚林&#xff0c;王海青. 信号与系统&#xff08;第五版&#xff09;. 北京&#xff1a;电子工业出版社 [2] 郑君里&#xff0c;应…...

wsl(ubuntu)创建用户

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

[足式机器人]Part2 Dr. CAN学习笔记-自动控制原理Ch1-8Lag Compensator滞后补偿器

本文仅供学习使用 本文参考&#xff1a; B站&#xff1a;DR_CAN Dr. CAN学习笔记-自动控制原理Ch1-8Lag Compensator滞后补偿器 从稳态误差入手&#xff08;steady state Error&#xff09; 误差 Error &#xff1a; 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架构&#xff08;5个协议&#xff09; 题目1答案点 Handshake Proto…...

Golang高质量编程与性能调优实战

1.1 简介 高质量:编写的代码能否达到正确可靠、简洁清晰的目标 各种边界条件是否考虑完备异常情况处理,稳定性保证易读易维护编程原则 简单性 消除多余的重复性,以简单清晰的逻辑编写代码不理解的代码无法修复改进可读性 代码是写给人看的,并不是机器编写可维护代码的第一…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...

SQL注入篇-sqlmap的配置和使用

在之前的皮卡丘靶场第五期SQL注入的内容中我们谈到了sqlmap&#xff0c;但是由于很多朋友看不了解命令行格式&#xff0c;所以是纯手动获取数据库信息的 接下来我们就用sqlmap来进行皮卡丘靶场的sql注入学习&#xff0c;链接&#xff1a;https://wwhc.lanzoue.com/ifJY32ybh6vc…...