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

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. 旋转数组的最小数字】

题目 把一个数组最开始的若干个元素搬到数组的末尾&#xff0c;我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers &#xff0c;它原来是一个升序排列的数组&#xff0c;并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如&#xff0c;数组 [3,4…...

git教程(第一次使用)

一、gitee和github区别 二、git使用 下载地址 windows&#xff1a;https://gitforwindows.org/ mac&#xff1a;http://sourceforge.net/projects/git-osx-installer/ 1.git初次运行前的配置 &#xff08;1&#xff09;配置用户信息 git config --global user.name "…...

Autoware.ai1.14.0自动驾驶-Demo运行

Autoware.ai1.14.0自动驾驶-Demo运行 数据准备 下载数据&#xff1a; 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 中的一个接口&#xff0c;&#xff0c;用于实体属性和 数据库字段&#xff0c;&#xff0c;之间的转换&#xff0c;&#xff0c;&#xff0c;类似mybatis中的typeHandler AttributeConverter使用 定义一个类实现AttributeConverter接口&#xff0c…...

【逗老师的PMP学习笔记】8、项目质量管理

目录 一、规划质量管理1、质量管理的发展历史2、戴明环&#xff0c;PDCA理论3、【关键输入】事业环境因素4、【关键输入】成本效益分析5、【关键工具】质量成本6、【关键输出】质量管理计划7、插一嘴&#xff0c;项目的三个标准8、【关键工具】质量测量指标 二、管理质量1、【关…...

Zookeeper集群

目录 一、Zookeeper 概述 1&#xff09;Zookeeper 定义 2&#xff09;Zookeeper 工作机制 3&#xff09;Zookeeper 特点 4&#xff09;Zookeeper 数据结构 5&#xff09;Zookeeper 应用场景 6&#xff09;Zookeeper 选举机制 ●第一次启动选举机制 ●非第一次启动选举机…...

后端进阶之路——Spring Security构建强大的身份验证和授权系统(四)

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 「推荐专栏」&#xff1a; ★java一站式服务 ★ ★前端炫酷代码分享 ★ ★ uniapp-从构建到提升★ ★ 从0到英雄&#xff0c;vue成神之路★ ★ 解决算法&#xff0c;一个专栏就够了★ ★ 架…...

【香瓜说职场】第10月(2018.01.29)

自从17年4月份开始辞职创业&#xff0c;已经10个月了。聊聊近况。 一、博客被冻结 冻结原因是我把博客的积分放在淘宝店铺售卖&#xff0c;卖一周就被查了。 我的每个积分售卖0.5元&#xff0c;是全网最低&#xff0c;每个资源下载一般需要2、3个积分。售…...

​LeetCode解法汇总1749. 任意子数组和的绝对值的最大值

目录链接&#xff1a; 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目&#xff1a; https://github.com/September26/java-algorithms 原题链接&#xff1a;力扣 描述&#xff1a; 给你一个整数数组 nums 。一个子数组 [numsl, numsl1, ..., numsr-1, numsr] 的…...

4.2、Flink任务怎样读取文件中的数据

目录 1、前言 2、readTextFile&#xff08;已过时&#xff0c;不推荐使用&#xff09; 3、readFile&#xff08;已过时&#xff0c;不推荐使用&#xff09; 4、fromSource(FileSource) 推荐使用 1、前言 思考: 读取文件时可以设置哪些规则呢&#xff1f; 1. 文件的格式(tx…...

Effective Java笔记(28)列表优于数组

数组与泛型相比&#xff0c;有两个重要的不同点 。 首先&#xff0c;数组是协变的&#xff08; covariant &#xff09; 。 这个词听起来有点吓人&#xff0c;其实只是表示如果 Sub 为 Super 的子类型&#xff0c;那么数组类型 Sub[ ]就是Super[ ]的子类型。 相反&#xff0c;泛…...

做BI领域的ChatGPT,思迈特升级一站式ABI平台

8月8日&#xff0c;以「指标驱动 智能决策」为主题&#xff0c;2023 Smartbi V11系列新品发布会在广州丽思卡尔顿酒店开幕。 ​ 后疫情时代&#xff0c;BI发展趋势的观察与应对 在发布会上&#xff0c;思迈特CEO吴华夫在开场致辞中表示&#xff0c;当前大环境背景下&#xf…...

ELFK——ELK结合filebeat日志分析系统(2)

目录 一、filebeat 二、ELFK 1.原理简介 2.在ELK基础上部署filebeat 一、filebeat Filebeat&#xff0c;轻量级的开源日志文件数据搜集器。通常在需要采集数据的客户端安装 Filebeat&#xff0c;并指定目录与日志格式&#xff0c;Filebeat 就能快速收集数据&#xff0c;并…...

webSocket 协议是什么

webSocket 协议是什么&#xff0c;能简述一下吗&#xff1f; websocket 协议 HTML5 带来的新协议&#xff0c;相对于 http&#xff0c;它是一个持久连接的协议&#xff0c;它利用 http 协议完成握手&#xff0c;然后通过 TCP 连接通道发送消息&#xff0c;使用 websocket 协议可…...

CentOS 7迁移Anolis OS 8

背景&#xff1a;生产环境客户要求操作系统国产化 操作系统&#xff1a;Centos7.9 内核&#xff1a;5.4.108 服务器可以联网&#xff0c;进行在线迁移&#xff1a; # 下载迁移工具软件源 wget https://mirrors.openanolis.cn/anolis/migration/anolis-migration.repo -O /etc/y…...

Transformer 立体视觉 Depth Estimation

1. Intro 立体深度估计具有重要的意义,因为它能够重建三维信息。为此,在左右相机图像之间匹配相应的像素;对应像素位置的差异,即视差,可以用来推断深度并重建3D场景。最近基于深度学习的立体深度估计方法已经显示出有希望的结果,但仍然存在一些挑战。 其中一个挑战涉及使…...

vue去掉所有输入框两边空格,封装指令去空格,支持Vue2和Vue3,ElementUI Input去空格

需求背景 就是页面很多表单输入框&#xff0c;期望在提交的时候&#xff0c;都要把用户两边的空格去掉 ❌使用 vue 的指令 .trim 去掉空格 中间会输入不了空格&#xff0c; 比如我想输入 你好啊 中国, 这中间的空格输入不了&#xff0c;只能变成 你好啊中国 ❌在提交的时候使用…...

认识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 大屏数字滚动效果

父组件&#xff1a; <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实现)

深度学习中的注意力机制&#xff08;Attention Mechanism&#xff09;是一种模仿人类视觉和认知系统的方法&#xff0c;它允许神经网络在处理输入数据时集中注意力于相关的部分。通过引入注意力机制&#xff0c;神经网络能够自动地学习并选择性地关注输入中的重要信息&#xff…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...