LeetCode-热题100:153. 寻找旋转排序数组中的最小值
题目描述
已知一个长度为 n
的数组,预先按照升序排列,经由 1
到 n
次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7]
在变化后可能得到:
若旋转 4
次,则可以得到 [4,5,6,7,0,1,2]
若旋转 7
次,则可以得到 [0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。
给你一个元素值 互不相同 的数组 nums
,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入: nums = [3,4,5,1,2]
输出: 1
解释: 原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
示例 2:
输入: nums = [4,5,6,7,0,1,2]
输出: 0
解释: 原数组为 [0,1,2,4,5,6,7] ,旋转 3 次得到输入数组。
示例 3:
输入: nums = [11,13,15,17]
输出: 11
解释: 原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。
提示:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
- `nums 中的所有整数 互不相同
nums
原来是一个升序排序的数组,并进行了1
至n
次旋转
代码及注释
func findMin(nums []int) int {left, right := 0, len(nums) - 1 // 循环直到左指针超过右指针for left <= right {// 如果右指针对应的值大于或等于左指针对应的值,说明数组是升序的,直接返回左指针对应的值if nums[right] >= nums[left] {return nums[left]}// 如果只剩下两个元素,返回右指针对应的值,因为数组升序已经判断过了,因此这里直接可以知道nums[right] < nums[left]if right - left == 1 {return nums[right]}mid := (left + right) / 2// 如果中间值是最小值,返回中间值if nums[mid] <= nums[mid - 1] && nums[mid] <= nums[mid + 1] {return nums[mid]}// 如果中间值大于等于左指针对应的值,说明最小值在右半部分,更新左指针if nums[mid] >= nums[left] {left = mid + 1} else { // 否则,最小值在左半部分,更新右指针right = mid - 1}}return 0
}
代码解释
-
初始化左右指针:
left
指向数组的第一个元素。right
指向数组的最后一个元素。
-
循环查找最小值:
- 如果
nums[right] >= nums[left]
,说明数组是升序的,直接返回nums[left]
。 - 如果只剩下两个元素 (
right - left == 1
),因为数组升序已经判断过了,因此这里直接可以知道nums[right] < nums[left],返回nums[right]
。 - 计算中间值
mid
。 - 如果
nums[mid] <= nums[mid - 1] && nums[mid] <= nums[mid + 1]
,说明mid
是最小值,返回nums[mid]
。 - 如果
nums[mid] >= nums[left]
,说明最小值在mid
右侧,更新left = mid + 1
。 - 否则,最小值在
mid
左侧,更新right = mid - 1
。
- 如果
这段代码的时间复杂度是 O(log n),其中 n 是数组 nums
的长度。
相关文章:
LeetCode-热题100:153. 寻找旋转排序数组中的最小值
题目描述 已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到: 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次…...
游戏客户客户端面经
C#和C的类的区别C# List添加100个Obj和100 int内存是怎么变化的重载和重写的区别,重载是怎么实现的重写是怎么实现的?虚函数表是类的还是对象的用过哪些C的STLVector底层是怎么实现的Vector添加一百次数据内存是怎么变化Map的底层,红黑树的查…...

网站业务对接DDoS高防
准备需要接入的网站域名清单,包含网站的源站服务器IP(仅支持公网IP的防护)、端口信息等。所接入的网站域名必须已完成ICP备案。如果您的网站支持HTTPS协议访问,您需要准备相应的证书和私钥信息,一般包含格式为.crt的公…...

Python-VBA编程500例-024(入门级)
字符串写入的行数(Line Count For String Writing)在实际应用中有着广泛的应用场景。常见的应用场景有: 1、文本编辑及处理:在编写或编辑文本文件时,如使用文本编辑器或文本处理器,经常需要处理字符串并确定其在文件中的行数。这…...

蓝桥杯 - 小明的背包1(01背包)
解题思路: 本题属于01背包问题,使用动态规划 dp[ j ]表示容量为 j 的背包的最大价值 注意: 需要时刻提醒自己dp[ j ]代表的含义,不然容易晕头转向 注意越界问题,且 j 需要倒序遍历 如果正序遍历 dp[1] dp[1 - vo…...
学习java第二十六天
Spring是一个开源框架,Spring是一个轻量级的Java 开发框架。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构,分层架构允许使用者选择使用哪一个组件,同时为 J2EE 应用程序开发提供集成的框架。Spring使用基本的…...

Go第三方框架--gin框架(二)
4. gin框架源码–Engine引擎和压缩前缀树的建立 讲了这么多 到标题4才开始介绍源码,主要原因还是想先在头脑中构建起 一个大体的框架 然后再填肉 这样不容易得脑血栓。标题四主要涉及标题2.3的步骤一 也就是 标题2.3中的 粗线框中的内容 4.1 Engine 引擎的建立 见…...

五分钟搞懂UDS刷写34/36/37服务(内含S19文件解读)
目录 34服务 36服务 37服务 S19文件介绍 理论太多总是让人头昏,通过举例的方法学习刷写是最好的办法,刷写中最重要的就是34/36/37服务之间的联动,在我当前的项目中37服务较为简单,等待36服务全部传输完成之后,发送…...
知识图谱智能问答系统技术实现
知识图谱是以一种结构化的方式存储和描述知识的数据集合,它将知识表示为节点和边的形式,并可以对这些节点和边进行有意义的存储、查询、连接和关系挖掘等操作。知识图谱不仅可以为人提供理解信息的能力,而且还能为机器提供对信息进行分析、推…...

【unity】如何汉化unity编译器
在【unity】如何汉化unity Hub这篇文章中,我们已经完成了unity Hub的汉化,现在让我们对unity Hub安装的编译器也进行下汉化处理。 第一步:在unity Hub软件左侧栏目中点击安装,选择需要汉化的编译器,再点击设置图片按钮…...

为什么Python不适合写游戏?
知乎上有热门个问题:Python 能写游戏吗?有没有什么开源项目? Python可以开发游戏,但不是好的选择 Python作为脚本语言,一般很少用来开发游戏,但也有不少大型游戏有Python的身影,比如࿱…...

查询优化-提升子查询-UNION类型
瀚高数据库 目录 文档用途 详细信息 文档用途 剖析UNION类型子查询提升的条件和过程 详细信息 注:图片较大,可在浏览器新标签页打开。 SQL: SELECT * FROM score sc, LATERAL(SELECT * FROM student WHERE sno 1 UNION ALL SELECT * FROM student…...

【数据结构 | 图论】如何用链式前向星存图(保姆级教程,详细图解+完整代码)
一、概述 链式前向星是一种用于存储图的数据结构,特别适合于存储稀疏图,它可以有效地存储图的边和节点信息,以及边的权重。 它的主要思想是将每个节点的所有出边存储在一起,通过数组的方式连接(类似静态数组实现链表…...

气象预测新篇章:Python人工智能的变革力量
Python是功能强大、免费、开源,实现面向对象的编程语言,在数据处理、科学计算、数学建模、数据挖掘和数据可视化方面具备优异的性能,这些优势使得Python在气象、海洋、地理、气候、水文和生态等地学领域的科研和工程项目中得到广泛应用。可以…...

基于微信小程序的民宿短租系统设计与实现(论文+源码)_kaic
摘 要 随着社会的发展,出差、旅游成为常态,也就造成民宿短租市场的兴起。人们新到陌生的环境里找民宿一般都是通过中介。中介虽然可以快速找到合适的民宿但会收取大量的中介费用,这对刚到新环境里的人们来说是一笔大的资金支出。也有一些人通…...

vue3开发前端表单缓存自定义指令,移动端h5必备插件
开发背景 公司需要开发一款移动端应用,使用vue开发,用户录入表单需要本地缓存,刷新页面,或者不小心关掉重新进来,上次录入的信息还要存在。 这里有两种方案,第一种就是像博客平台一样,实时保存…...

骗子查询系统源码
源码简介 小权云黑管理系统 V1.0 功能如下: 1.添加骗子,查询骗子 2.可添加团队后台方便审核用 3.在线反馈留言系统 4.前台提交骗子,后台需要审核才能过 5.后台使用光年UI界面 6.新增导航列表,可给网站添加导航友链 7.可添加云黑类…...

目标检测+车道线识别+追踪
一种方法: 车道线检测-canny边缘检测-霍夫变换 一、什么是霍夫变换 霍夫变换(Hough Transform)是一种在图像处理和计算机视觉中广泛使用的特征检测技术,主要用于识别图像中的几何形状,尤其是直线、圆和椭圆等常见形状…...

非wpf应用程序项目【类库、用户控件库】中使用HandyControl
文章速览 前言参考文章实现方法1、添加HandyControl包;2、添加资源字典3、修改资源字典内容 坚持记录实属不易,希望友善多金的码友能够随手点一个赞。 共同创建氛围更加良好的开发者社区! 谢谢~ 前言 wpf应用程序中,在入口项目中…...

【python】flask执行上下文context,请求上下文和应用上下文原理解析
✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...

如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...

使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...