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

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] ,旋转 4 次得到输入数组。
示例 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 次旋转

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路:

其实题目有一个隐含条件,那就是如果数组旋转过且不为递增的顺序,那么最左侧的值一定是大于最右侧的值的,所以我们根据判断下标为mid处数组的值与下标为h处的值即可锁定最小值所在的范围,如果nums[mid]小于nums[h],那么最小值可能出现在l~mid处,反之,最小值出现在mid+1~h处。

代码实现如下:

class Solution {public int findMin(int[] nums) {int l = 0;int h = nums.length - 1;while (l < h) {int mid = l + (h - l) / 2;if (nums[mid] < nums[h]) {h = mid;} else {l = mid + 1;}}return nums[l];}
}

 

相关文章:

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 次&#xff0…...

Linux 文件描述符

Linux 文件描述符 Linux 中一切皆文件&#xff0c;比如 C 源文件、视频文件、Shell脚本、可执行文件等&#xff0c;就连键盘、显示器、鼠标等硬件设备也都是文件。 一个 Linux 进程可以打开成百上千个文件&#xff0c;为了表示和区分已经打开的文件&#xff0c;Linux 会给每个…...

第17章_反射机制

第17章_反射机制 讲师&#xff1a;尚硅谷-宋红康&#xff08;江湖人称&#xff1a;康师傅&#xff09; 官网&#xff1a;http://www.atguigu.com 本章专题与脉络 1. 反射(Reflection)的概念 1.1 反射的出现背景 Java程序中&#xff0c;所有的对象都有两种类型&#xff1a;编…...

使用VBA小程序提高资产清查效率

资产清查是一件相当烦人的工作&#xff0c;去年使用LayUIPHPMS SQL Server 2014写了一个资产清查的程序&#xff0c;可惜写完了&#xff0c;LayUI已经停止更新了&#xff0c;就没有再完善下去&#xff0c;数据也没有更新&#xff0c;等于就废了。 今年又要进行资产清查&#xf…...

JavaSE学习进阶day07_02 异常

第三章 异常 3.1 异常概念 异常&#xff0c;就是不正常的意思。在生活中:医生说,你的身体某个部位有异常,该部位和正常相比有点不同,该部位的功能将受影响.在程序中的意思就是&#xff1a; 异常 &#xff1a;指的是程序在执行过程中&#xff0c;出现的非正常的情况&#xff0…...

操作系统学习笔记

文章目录 操作系统虚拟内存锁缓存机制CPU性能指标进程、线程文件管理系统 操作系统 操作系统是控制应用程序的执行&#xff0c;并充当应用程序和计算机硬件之间的接口。在计算机系统中&#xff0c;处于最外层的是&#xff08;应用软件&#xff09; 。 面向用户的就是外层的&am…...

【Spring Boot】SpringBoot设计了哪些可拓展的机制?

文章目录 前言SpringBoot核心源码拓展Initializer拓展监听器ApplicationListenerBeanFactory的后置处理器 & Bean的后置处理器AOP其他的拓展点 前言 当我们引入注册中心的依赖&#xff0c;比如nacos的时候&#xff0c;当我们启动springboot&#xff0c;这个服务就会根据配置…...

《程序员面试金典(第6版)》面试题 10.10. 数字流的秩

题目描述 假设你正在读取一串整数。每隔一段时间&#xff0c;你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作&#xff0c;也就是说&#xff1a; 实现 track(int x) 方法&#xff0c;每读入一个数字都会调用该方法&#xff1b; 实现 g…...

智能洗地机好用吗?值得入手的洗地机推荐

洗地机是一款高效的地面清洁设备&#xff0c;不仅可以很好清理地面不同形态的干湿垃圾&#xff0c;还减少了人工和水资源的浪费&#xff0c;是我们日常生活中必不可少的清洁工具。作为以一位评测博主&#xff0c;很多朋友咨询我在选购洗地机时应该注意哪些要点&#xff0c;有哪…...

Spring Security实战(一)——基于内存和数据库模型的认证与授权

目录 简介 一、初识Spring Security&#xff08;入门案例&#xff09; &#xff08;1&#xff09;新建project &#xff08;2&#xff09;选择依赖 &#xff08;3&#xff09;编写一个 HelloController &#xff08;4&#xff09;启动项目&#xff0c;访问localhost:8080…...

轻松掌握FFmpeg编程:从架构到实践

轻松掌握FFmpeg编程&#xff1a;从架构到实践 (Master FFmpeg Programming with Ease: From Architecture to Practice 引言 (Introduction)FFmpeg简介与应用场景 (Brief Introduction and Application Scenarios of FFmpeg)为什么选择FFmpeg进行音视频处理 (Why Choose FFmpeg…...

桌面应用程序开发攻略(初步了解)

什么是桌面应用程序&#xff1f; 桌面应用开发是指为桌面计算机或其他类似设备&#xff08;如服务器&#xff09;开发软件应用程序的过程。桌面应用通常是独立于浏览器运行的&#xff0c;并且可以在操作系统的桌面或应用程序菜单中找到。桌面应用可以使用各种编程语言开发&…...

【李老师云计算】HBase+Zookeeper部署及Maven访问(HBase集群实验)

索引 前言1. Zookeeper1.1 主机下载Zookeeper安装包1.2 主机解压Zookeeper1.3 ★解决解压后文件缺失1.4 主机配置Zookeeper文件1.4.1 配置zoo_sample.cfg文件1.4.2 配置/data/myid文件 1.5 主机传输Zookeeper文件到从机1.6 从机修改Zookeeper文件1.6.1 修改zoo.cfg文件1.6.2 修…...

第11章_常用类和基础API

第11章_常用类和基础API 讲师&#xff1a;尚硅谷-宋红康&#xff08;江湖人称&#xff1a;康师傅&#xff09; 官网&#xff1a;http://www.atguigu.com 本章专题与脉络 1. 字符串相关类之不可变字符序列&#xff1a;String 1.1 String的特性 java.lang.String 类代表字符串…...

Java语言数据类型与c语言数据类型的不同

目录 一、c语言数据类型 1.基本类型&#xff1a; 2.枚举类型&#xff1a; 3.空类型&#xff1a; 4.派生类型&#xff1a; 二、C语言编程需要注意的64位和32机器的区别 三、 不同之处 一、c语言数据类型 首先&#xff0c;先来整体介绍一下C语言的数据类型分类。 1.基…...

C# Replace()、Trim()、Split()、Substring()、IndexOf() 、 LastIndexOf()函数

目录 一、Replace() 二、Trim() 三、Split() 四、Substring() 五、IndexOf() 六、LastIndexOf() 一、Replace() 在C#中&#xff0c;Replace()是一个字符串方法&#xff0c;用于将指定的字符或子字符串替换为另一个字符或字符串。下面是一些Replace()方法的常见用法和示例…...

C++类的理解与类型名,类的成员,两种定义方式,类的访问限定符,成员访问,作用域与实例化对象

面向过程和面向对象初步认识 C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题的步骤&#xff0c;通过函数调用逐步解决问题 C是基于面向对象的&#xff0c;关注的是对象&#xff0c;将一件事情拆分成不同的对象&#xff0c;靠对象之间的交互完成 面向…...

【华为OD机试真题 C++】1051 - 处理器问题 | 机试题+算法思路+考点+代码解析

文章目录 一、题目&#x1f538;题目描述&#x1f538;输入输出&#x1f538;样例1&#x1f538;样例2 二、题目解析三、代码参考 作者&#xff1a;KJ.JK &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &…...

Linux 常用操作命令大全

一、基础知识 1.1 Linux系统的文件结构 /bin 二进制文件&#xff0c;系统常规命令 /boot 系统启动分区&#xff0c;系统启动时读取的文件 /dev 设备文件 /etc 大多数配置文件 /home 普通用户的家目录 /lib 32位函数库 /lib64 64位库 /media 手动临时挂载点 /mnt 手动临时挂载点…...

Git使用教程

Git 目标 Git简介【了解】 使用Git管理文件版本【重点】 远程仓库使用【掌握】 分支管理【重点】 远程仓库【掌握】 一、Git简介 1、版本控制系统简介 1.1、版本控制前生今世 版本控制系统Version Control Systems&#xff0c;简称 VCS是将『什么时候、谁、对什么文件…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

2.3 物理层设备

在这个视频中&#xff0c;我们要学习工作在物理层的两种网络设备&#xff0c;分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间&#xff0c;需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质&#xff0c;假设A节点要给…...

FOPLP vs CoWoS

以下是 FOPLP&#xff08;Fan-out panel-level packaging 扇出型面板级封装&#xff09;与 CoWoS&#xff08;Chip on Wafer on Substrate&#xff09;两种先进封装技术的详细对比分析&#xff0c;涵盖技术原理、性能、成本、应用场景及市场趋势等维度&#xff1a; 一、技术原…...