Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】
题目
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的最小值为 1。
注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
示例 1:
输入:numbers = [3,4,5,1,2]
输出:1
示例 2:
输入:numbers = [2,2,2,0,1]
输出:0
提示:
- n == numbers.length
- 1 <= n <= 5000
- -5000 <= numbers[i] <= 5000
- numbers 原来是一个升序排序的数组,并进行了 1 至 n 次旋转
解题思路
1.题目要求我们返回旋转数组的最小元素,我们可以使用二分查找找到旋转排序数组中的最小元素。
2.首先初始化两个指针`left`和`right`,它们分别表示数组的起始和结束索引。在while循环内部,它检查`left`索引处的元素是否小于`right`索引处的元素。如果是,则意味着数组已经按升序排序,最小元素位于`left`索引处。因此,它返回`left`索引处的元素。如果数组未排序,则计算`mid`索引为`left`和`right`的平均值。
3.然后,它将`mid`索引处的元素与`left`索引处的元素进行比较。如果`mid`索引处的元素大于`left`索引处的元素,则意味着最小元素位于数组的右半部分。因此,它将`left`指针更新为`mid + 1`。如果`mid`索引处的元素小于`left`索引处的元素,则意味着最小元素位于数组的左半部分。因此,它将`right`指针更新为`mid`。如果`mid`索引处的元素等于`left`索引处的元素,则意味着数组中存在重复元素。在这种情况下,它将`left`指针增加1。
4.循环继续,直到`left`指针小于`right`指针为止。此时,`left`指针将指向数组中的最小元素,并返回`left`索引处的元素。如果循环退出时仍未找到最小元素,则意味着数组已经按升序排序,最小元素位于`left`索引处。因此,它返回`left`索引处的元素。
代码实现
class Solution {public int minArray(int[] numbers) {int left = 0;int right = numbers.length - 1;while(left < right){if(numbers[left] < numbers[right]){return numbers[left];}int mid = (left + right) / 2;if(numbers[mid] > numbers[left]){left = mid + 1;}else if(numbers[mid] < numbers[left]){right = mid;}else{left ++;}}return numbers[left];}}
测试结果


相关文章:
Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】
题目 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4…...
git教程(第一次使用)
一、gitee和github区别 二、git使用 下载地址 windows:https://gitforwindows.org/ mac:http://sourceforge.net/projects/git-osx-installer/ 1.git初次运行前的配置 (1)配置用户信息 git config --global user.name "…...
Autoware.ai1.14.0自动驾驶-Demo运行
Autoware.ai1.14.0自动驾驶-Demo运行 数据准备 下载数据: wget https://autoware-ai.s3.us-east-2.amazonaws.com/sample_moriyama_data.tar.gz wget https://autoware-ai.s3.us-east-2.amazonaws.com/sample_moriyama_150324.tar.gz一定要注意解压文件是在.auto…...
AttributeConverter
AttributeConverter 是 JPA 中的一个接口,,用于实体属性和 数据库字段,,之间的转换,,,类似mybatis中的typeHandler AttributeConverter使用 定义一个类实现AttributeConverter接口,…...
【逗老师的PMP学习笔记】8、项目质量管理
目录 一、规划质量管理1、质量管理的发展历史2、戴明环,PDCA理论3、【关键输入】事业环境因素4、【关键输入】成本效益分析5、【关键工具】质量成本6、【关键输出】质量管理计划7、插一嘴,项目的三个标准8、【关键工具】质量测量指标 二、管理质量1、【关…...
Zookeeper集群
目录 一、Zookeeper 概述 1)Zookeeper 定义 2)Zookeeper 工作机制 3)Zookeeper 特点 4)Zookeeper 数据结构 5)Zookeeper 应用场景 6)Zookeeper 选举机制 ●第一次启动选举机制 ●非第一次启动选举机…...
后端进阶之路——Spring Security构建强大的身份验证和授权系统(四)
前言 「作者主页」:雪碧有白泡泡 「个人网站」:雪碧的个人网站 「推荐专栏」: ★java一站式服务 ★ ★前端炫酷代码分享 ★ ★ uniapp-从构建到提升★ ★ 从0到英雄,vue成神之路★ ★ 解决算法,一个专栏就够了★ ★ 架…...
【香瓜说职场】第10月(2018.01.29)
自从17年4月份开始辞职创业,已经10个月了。聊聊近况。 一、博客被冻结 冻结原因是我把博客的积分放在淘宝店铺售卖,卖一周就被查了。 我的每个积分售卖0.5元,是全网最低,每个资源下载一般需要2、3个积分。售…...
LeetCode解法汇总1749. 任意子数组和的绝对值的最大值
目录链接: 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:力扣 描述: 给你一个整数数组 nums 。一个子数组 [numsl, numsl1, ..., numsr-1, numsr] 的…...
4.2、Flink任务怎样读取文件中的数据
目录 1、前言 2、readTextFile(已过时,不推荐使用) 3、readFile(已过时,不推荐使用) 4、fromSource(FileSource) 推荐使用 1、前言 思考: 读取文件时可以设置哪些规则呢? 1. 文件的格式(tx…...
Effective Java笔记(28)列表优于数组
数组与泛型相比,有两个重要的不同点 。 首先,数组是协变的( covariant ) 。 这个词听起来有点吓人,其实只是表示如果 Sub 为 Super 的子类型,那么数组类型 Sub[ ]就是Super[ ]的子类型。 相反,泛…...
做BI领域的ChatGPT,思迈特升级一站式ABI平台
8月8日,以「指标驱动 智能决策」为主题,2023 Smartbi V11系列新品发布会在广州丽思卡尔顿酒店开幕。 后疫情时代,BI发展趋势的观察与应对 在发布会上,思迈特CEO吴华夫在开场致辞中表示,当前大环境背景下…...
ELFK——ELK结合filebeat日志分析系统(2)
目录 一、filebeat 二、ELFK 1.原理简介 2.在ELK基础上部署filebeat 一、filebeat Filebeat,轻量级的开源日志文件数据搜集器。通常在需要采集数据的客户端安装 Filebeat,并指定目录与日志格式,Filebeat 就能快速收集数据,并…...
webSocket 协议是什么
webSocket 协议是什么,能简述一下吗? websocket 协议 HTML5 带来的新协议,相对于 http,它是一个持久连接的协议,它利用 http 协议完成握手,然后通过 TCP 连接通道发送消息,使用 websocket 协议可…...
CentOS 7迁移Anolis OS 8
背景:生产环境客户要求操作系统国产化 操作系统:Centos7.9 内核:5.4.108 服务器可以联网,进行在线迁移: # 下载迁移工具软件源 wget https://mirrors.openanolis.cn/anolis/migration/anolis-migration.repo -O /etc/y…...
Transformer 立体视觉 Depth Estimation
1. Intro 立体深度估计具有重要的意义,因为它能够重建三维信息。为此,在左右相机图像之间匹配相应的像素;对应像素位置的差异,即视差,可以用来推断深度并重建3D场景。最近基于深度学习的立体深度估计方法已经显示出有希望的结果,但仍然存在一些挑战。 其中一个挑战涉及使…...
vue去掉所有输入框两边空格,封装指令去空格,支持Vue2和Vue3,ElementUI Input去空格
需求背景 就是页面很多表单输入框,期望在提交的时候,都要把用户两边的空格去掉 ❌使用 vue 的指令 .trim 去掉空格 中间会输入不了空格, 比如我想输入 你好啊 中国, 这中间的空格输入不了,只能变成 你好啊中国 ❌在提交的时候使用…...
认识FFMPEG框架
FFMPEG全称: Fast Forward Moving Picture Experts Group (MPEG:动态图像专家组) ffmpeg相关网站: git://source.ffmpeg.org/ffmpeg.git http://git.videolan.org/?pffmpeg.git https://github.com/FFmpeg/FFmpeg FFMPEG框架基本组件: AVFormat , AVCodec, AVDevice, AVFil…...
Vue3 大屏数字滚动效果
父组件: <template> <div class"homePage"> <NumRoll v-for"(v, i) in numberList" :key"i" :number"v"></NumRoll> </div> </template> <script setup> import { onMounted, r…...
【深度学习注意力机制系列】—— SENet注意力机制(附pytorch实现)
深度学习中的注意力机制(Attention Mechanism)是一种模仿人类视觉和认知系统的方法,它允许神经网络在处理输入数据时集中注意力于相关的部分。通过引入注意力机制,神经网络能够自动地学习并选择性地关注输入中的重要信息ÿ…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果是一个支持网页浏览器进行实时语音…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...
恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...
