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

LeetCode-热题100:153. 寻找旋转排序数组中的最小值

题目描述

已知一个长度为 n 的数组,预先按照升序排列,经由 1n旋转 后,得到输入数组。例如,原数组 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 原来是一个升序排序的数组,并进行了 1n 次旋转

代码及注释

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
}

代码解释

  1. 初始化左右指针:

    • left 指向数组的第一个元素。
    • right 指向数组的最后一个元素。
  2. 循环查找最小值:

    • 如果 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 的数组&#xff0c;预先按照升序排列&#xff0c;经由 1 到 n 次 旋转 后&#xff0c;得到输入数组。例如&#xff0c;原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到&#xff1a; 若旋转 4 次&#xff0c;则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次…...

游戏客户客户端面经

C#和C的类的区别C# List添加100个Obj和100 int内存是怎么变化的重载和重写的区别&#xff0c;重载是怎么实现的重写是怎么实现的&#xff1f;虚函数表是类的还是对象的用过哪些C的STLVector底层是怎么实现的Vector添加一百次数据内存是怎么变化Map的底层&#xff0c;红黑树的查…...

网站业务对接DDoS高防

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

Python-VBA编程500例-024(入门级)

字符串写入的行数(Line Count For String Writing)在实际应用中有着广泛的应用场景。常见的应用场景有&#xff1a; 1、文本编辑及处理&#xff1a;在编写或编辑文本文件时&#xff0c;如使用文本编辑器或文本处理器&#xff0c;经常需要处理字符串并确定其在文件中的行数。这…...

蓝桥杯 - 小明的背包1(01背包)

解题思路&#xff1a; 本题属于01背包问题&#xff0c;使用动态规划 dp[ j ]表示容量为 j 的背包的最大价值 注意&#xff1a; 需要时刻提醒自己dp[ j ]代表的含义&#xff0c;不然容易晕头转向 注意越界问题&#xff0c;且 j 需要倒序遍历 如果正序遍历 dp[1] dp[1 - vo…...

学习java第二十六天

Spring是一个开源框架&#xff0c;Spring是一个轻量级的Java 开发框架。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构&#xff0c;分层架构允许使用者选择使用哪一个组件&#xff0c;同时为 J2EE 应用程序开发提供集成的框架。Spring使用基本的…...

Go第三方框架--gin框架(二)

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

五分钟搞懂UDS刷写34/36/37服务(内含S19文件解读)

目录 34服务 36服务 37服务 S19文件介绍 理论太多总是让人头昏&#xff0c;通过举例的方法学习刷写是最好的办法&#xff0c;刷写中最重要的就是34/36/37服务之间的联动&#xff0c;在我当前的项目中37服务较为简单&#xff0c;等待36服务全部传输完成之后&#xff0c;发送…...

知识图谱智能问答系统技术实现

知识图谱是以一种结构化的方式存储和描述知识的数据集合&#xff0c;它将知识表示为节点和边的形式&#xff0c;并可以对这些节点和边进行有意义的存储、查询、连接和关系挖掘等操作。知识图谱不仅可以为人提供理解信息的能力&#xff0c;而且还能为机器提供对信息进行分析、推…...

【unity】如何汉化unity编译器

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

为什么Python不适合写游戏?

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

查询优化-提升子查询-UNION类型

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

【数据结构 | 图论】如何用链式前向星存图(保姆级教程,详细图解+完整代码)

一、概述 链式前向星是一种用于存储图的数据结构&#xff0c;特别适合于存储稀疏图&#xff0c;它可以有效地存储图的边和节点信息&#xff0c;以及边的权重。 它的主要思想是将每个节点的所有出边存储在一起&#xff0c;通过数组的方式连接&#xff08;类似静态数组实现链表…...

气象预测新篇章:Python人工智能的变革力量

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

基于微信小程序的民宿短租系统设计与实现(论文+源码)_kaic

摘 要 随着社会的发展&#xff0c;出差、旅游成为常态&#xff0c;也就造成民宿短租市场的兴起。人们新到陌生的环境里找民宿一般都是通过中介。中介虽然可以快速找到合适的民宿但会收取大量的中介费用&#xff0c;这对刚到新环境里的人们来说是一笔大的资金支出。也有一些人通…...

vue3开发前端表单缓存自定义指令,移动端h5必备插件

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

骗子查询系统源码

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

目标检测+车道线识别+追踪

一种方法&#xff1a; 车道线检测-canny边缘检测-霍夫变换 一、什么是霍夫变换 霍夫变换&#xff08;Hough Transform&#xff09;是一种在图像处理和计算机视觉中广泛使用的特征检测技术&#xff0c;主要用于识别图像中的几何形状&#xff0c;尤其是直线、圆和椭圆等常见形状…...

非wpf应用程序项目【类库、用户控件库】中使用HandyControl

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

【python】flask执行上下文context,请求上下文和应用上下文原理解析

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...