题目:

已知一个长度为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,它原来是一个升序排列的数组,并按上述情形进行了多次旋转,找出并返回数组中的最小元素。

 


题目:二分查找

一个不包含重复元素的升序数组在经过旋转之后,可以得到下面可视化的折线图:

 其中横轴表示数组元素的下标,纵轴表示数组元素的值。图中标出了最小值的位置,是我们需要查找的目标。

考虑数组中的最后一个元素x::在最小值右侧的元素(不包括最后一个元素本身),它们的值一定都严格小于 x;而在最小值左侧的元素,它们的值一定都严格大于 x。因此可以通过二分查找的方法找出最小值。

在二分查找的每一步中,左边界为 low,右边界为 high,区间的中点为 pivot,最小值就在该区间内。将中轴元素 nums[pivot] 与右边界元素 nums[high] 进行比较,

可能会有以下的三种情况:

第一种情况是 nums[pivot]<nums[high]。如下图所示,这说明 nums[pivot] 是最小值右侧的元素,因此我们可以忽略二分查找区间的右半部分。

第二种情况是 nums[pivot]>nums[high]。如下图所示,这说明 nums[pivot] 是最小值左侧的元素,因此我们可以忽略二分查找区间的左半部分。

 

由于数组不包含重复元素,并且只要当前的区间长度不为 1,pivot 就不会与 high 重合;而如果当前的区间长度为 1,这说明我们已经可以结束二分查找了。因此不会存在 nums[pivot]=nums[high] 的情况。

当二分查找结束时,就得到了最小值所在的位置。

class Solution(object):def findMin(self, nums):""":type nums: List[int]:rtype: int"""low,high=0,len(nums)-1 #初始化两个指针low和high,分别指向数组的开始(0)和结束位置while low<high:#当low指针小于high指针时继续循环mid=low+(high-low)//2  #计算中间位置if nums[mid]<nums[high]: #说明最小值在左半部分high=mid  #将右指针移动到中间位置else: #说明最小值在右半部分low=mid+1return nums[low]  #low == high,指向的就是最小值的位置

时间复杂度为: O(logn),其中 n 是数组 nums 的长度

空间复杂度:O(1)

源自力扣官方题解
 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/news/900645.shtml
繁体地址,请注明出处:http://hk.pswp.cn/news/900645.shtml
英文地址,请注明出处:http://en.pswp.cn/news/900645.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【MATLAB第113期】基于MATLAB的EFAST扩展傅里叶幅度敏感性分析方法(有目标函数)

【MATLAB第113期】基于MATLAB的EFAST扩展傅里叶幅度敏感性分析方法&#xff08;有目标函数&#xff09; 一、方法概述 扩展傅里叶幅度敏感性检验&#xff08;EFAST&#xff09;是一种基于频域分析的全局敏感性分析方法&#xff0c;能够同时评估模型参数的一阶敏感性&#xff…

Tiktok 关键字 视频及评论信息爬虫(1) [2025.04.07]

&#x1f64b;‍♀️Tiktok APP的基于关键字检索的视频及评论信息爬虫共分为两期&#xff0c;希望对大家有所帮助。 第一期见下文。 第二期&#xff1a;基于视频URL的评论信息爬取 1. Node.js环境配置 首先配置 JavaScript 运行环境&#xff08;如 Node.js&#xff09;&#x…

【愚公系列】《高效使用DeepSeek》058-选题策划

🌟【技术大咖愚公搬代码:全栈专家的成长之路,你关注的宝藏博主在这里!】🌟 📣开发者圈持续输出高质量干货的"愚公精神"践行者——全网百万开发者都在追更的顶级技术博主! 👉 江湖人称"愚公搬代码",用七年如一日的精神深耕技术领域,以"…

零基础教程:Windows电脑安装Linux系统(双系统/虚拟机)全攻略

一、安装方式选择 方案对比表 特性双系统安装虚拟机安装性能原生硬件性能依赖宿主机资源分配磁盘空间需要独立分区&#xff08;建议50GB&#xff09;动态分配&#xff08;默认20GB起&#xff09;内存占用独占全部内存需手动分配&#xff08;建议4GB&#xff09;启动方式开机选…

LeetCode 2968.执行操作使频率分数最大

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 你可以对数组执行 至多 k 次操作&#xff1a; 从数组中选择一个下标 i &#xff0c;将 nums[i] 增加 或者 减少 1 。 最终数组的频率分数定义为数组中众数的 频率 。 请你返回你可以得到的 最大 频率分数。 众数指的…

excel经验

Q:我现在有一个excel&#xff0c;有一列数据&#xff0c;大概两千多行。如何在这一列中 筛选出具有关键字的内容&#xff0c;并输出到另外一列中。 A: 假设数据在A列&#xff08;A1开始&#xff09;&#xff0c;关键字为“ABC”在相邻空白列&#xff08;如B1&#xff09;输入公…

HTTP查询参数示例(XMLHttpRequest查询参数)(带查询参数的HTTP接口示例——以python flask接口为例)flask查询接口

文章目录 HTTP查询参数请求示例接口文档——获取城市列表代码示例效果 带查询参数的HTTP接口示例——以python flask接口为例app.pyREADME.md运行应用API示例客户端示例关键实现说明&#xff1a;运行方法&#xff1a; HTTP查询参数请求示例 接口文档——获取城市列表 代码示例…

将飞帆制作的网页作为 div 集成到自己的网页中

并且自己的网页可以和飞帆中的控件相互调用函数。效果&#xff1a; 上链接 将飞帆制作的网页作为 div 集成到自己的网页中 - 文贝 进入可以复制、运行代码

Redis主从复制:告别单身Redis!

目录 一、 为什么需要主从复制&#xff1f;&#x1f914;二、 如何搭建主从架构&#xff1f;前提条件✅步骤&#x1f4c1; 创建工作目录&#x1f4dc; 创建 Docker Compose 配置文件&#x1f680; 启动所有 Redis&#x1f50d; 验证主从状态 &#x1f4a1; 重要提示和后续改进 …

k8s 1.30.6版本部署(使用canal插件)

#系统环境准备 参考 https://blog.csdn.net/dingzy1/article/details/147062698?spm1001.2014.3001.5501 #配置下载源 curl -fsSL https://mirrors.aliyun.com/kubernetes-new/core/stable/v1.30/deb/Release.key |gpg --dearmor -o /etc/apt/keyrings/kubernetes-apt-keyri…

机器学习的一百个概念(7)独热编码

前言 本文隶属于专栏《机器学习的一百个概念》&#xff0c;该专栏为笔者原创&#xff0c;引用请注明来源&#xff0c;不足和错误之处请在评论区帮忙指出&#xff0c;谢谢&#xff01; 本专栏目录结构和参考文献请见[《机器学习的一百个概念》 ima 知识库 知识库广场搜索&…

RHCSA复习

在Linux中&#xff0c; wrx 分别代表写&#xff08;write&#xff09;、读&#xff08;read&#xff09;和执行&#xff08;execute&#xff09;权限&#xff0c;它们对应的权限值分别是&#xff1a; - r &#xff08;读权限&#xff09;&#xff1a;权限值为4。 - w &am…

“乐企“平台如何重构业财税票全流程生态?

2025年&#xff0c;国家税务总局持续推进的"便民办税春风行动"再次推进数字化服务升级&#xff0c;其中"乐企"平台作为税务信息化的重要载体&#xff0c;持续优化数电票服务能力&#xff0c;为企业提供更高效、更规范的税务管理支持。在这一背景下&#xf…

Android audio(6)-audiopolicyservice介绍

AudioPolicyService 是策略的制定者&#xff0c;比如某种 Stream 类型不同设备的音量&#xff08;index/DB&#xff09;是多少、某种 Stream 类型的音频数据流对应什么设备等等。而 AudioFlinger 则是策略的执行者&#xff0c;例如具体如何与音频设备通信&#xff0c;维护现有系…

Boost库搜索引擎项目(版本1)

Boost库搜索引擎 项目开源地址 Github&#xff1a;https://github.com/H0308/BoostSearchingEngine Gitee&#xff1a;https://gitee.com/EPSDA/BoostSearchingEngine 版本声明 当前为最初版本&#xff0c;后续会根据其他内容对当前项目进行修改&#xff0c;具体见后续版本…

git分支合并信息查看

TortoiseGit工具 1、选择"Revision graph" 2、勾选view中的 Show branchings and merges Arrows point towards merges 3、图案说明 红色部分‌&#xff1a;代表当前分支 橙色部分‌&#xff1a;代表远程分支 黄色部分‌&#xff1a;代表一个tag 绿色部分‌&#xf…

Java学习笔记(多线程):ReentrantLock 源码分析

本文是自己的学习笔记&#xff0c;主要参考资料如下 JavaSE文档 1、AQS 概述1.1、锁的原理1.2、任务队列1.2.1、结点的状态变化 1.3、加锁和解锁的简单流程 2、ReentrantLock2.1、加锁源码分析2.1.1、tryAcquire()的具体实现2.1.2、acquirQueued()的具体实现2.1.3、tryLock的具…

在C++11及后续标准中,auto和decltype是用于类型推导的关键特性,它们的作用和用法。

在C11及后续标准中&#xff0c;auto和decltype是用于类型推导的关键特性&#xff0c;它们的作用和用法有所不同。以下是详细说明&#xff1a; 1. auto 关键字 基本作用 自动推导变量的类型&#xff08;根据初始化表达式&#xff09;主要用于简化代码&#xff0c;避免显式书写…

Linux:进程程序替换execl

目录 引言 1.单进程版程序替换 2.程序替换原理 3.6种替换函数介绍 3.1 函数返回值 3.2 命名理解 3.3 环境变量参数 引言 用fork创建子进程后执行的是和父进程相同的程序(但有可能执行不同的代码分支)&#xff0c;我们所创建的所有的子进程&#xff0c;执行的代码&#x…

LeetCode.02.04.分割链表

分割链表 给你一个链表的头节点 head 和一个特定值 x &#xff0c;请你对链表进行分隔&#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你不需要 保留 每个分区中各节点的初始相对位置。 示例 1&#xff1a; 输入&#xff1a;head [1,4,3,2,5,2], x …