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

每日一题——旋转数组的最小数字

题目


有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样的。请问,给定这样一个旋转数组,求数组中的最小值。

数据范围:1≤n≤10000,数组中任意元素的值: 0≤val≤10000

要求:空间复杂度:O(1) ,时间复杂度:O(logn)

示例1

输入:
[3,4,5,1,2]
返回值:
1

示例2

输入:
[3,100,200,3]
返回值:
3

思路


二分法:

  • mid = (start + end) / 2 为二分的中间位置。
  • mid,start,right分为三种情况:
    • nums[mid] > nums[end]时, 那么最小值一定在 [mid+1,end]区间中;
    • nums[mid] = nums[end]时,无法判断最小值在哪个区间,所以此时只能缩小end的值;
    • nums[mid] < nums[end]时,那么最小值一定在[start,mid]区间内。

解答代码


class Solution {
public:/*** @param nums int整型vector * @return int整型*/int minNumberInRotateArray(vector<int>& nums) {// write code hereint start = 0;int end = nums.size() - 1;while (start != end) {int mid = (start + end) / 2;if (nums[mid] > nums[end]) {//最小的数字在mid右边start = mid + 1;} else if (nums[mid] == nums[end]) {//无法判断,一个一个试end = end - 1;} else if (nums[mid] < nums[end]) {//最小数字要么是mid要么在mid左边end = mid;}}return nums[end];}
};

相关文章:

每日一题——旋转数组的最小数字

题目 有一个长度为 n 的非降序数组&#xff0c;比如[1,2,3,4,5]&#xff0c;将它进行旋转&#xff0c;即把一个数组最开始的若干个元素搬到数组的末尾&#xff0c;变成一个旋转数组&#xff0c;比如变成了[3,4,5,1,2]&#xff0c;或者[4,5,1,2,3]这样的。请问&#xff0c;给定这…...

SpringBoot Jackson 日期格式化统一配置

目录 1.在全局配置文件配置 2.通过JavaBean方式配置 1.在全局配置文件配置 spring:jackson:date-format: yyyy-MM-dd HH:mm:sstime-zone: GMT8 该配置方式仅支持 Date 类型的日期格式化&#xff0c;不支持LocalDate 及 LocalDateTime 的格式化。 2.通过JavaBean方式配置 …...

剑指 Offer 38. 字符串的排列 / LeetCode 47. 全排列 II(回溯法)

题目&#xff1a; 链接&#xff1a;剑指 Offer 38. 字符串的排列 难度&#xff1a;中等 输入一个字符串&#xff0c;打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组&#xff0c;但里面不能有重复元素。 示例: 输入&#xff1a;s “abc” 输出&…...

【前端知识】React 基础巩固(四十三)——Effect Hook

React 基础巩固(四十三)——Effect Hook 一、Effect Hook的基本使用 Effect Hook 用来完成一些类似class中生命周期的功能。 在使用类组件时&#xff0c;不管是渲染、网路请求还是操作DOM&#xff0c;其逻辑和代码是杂糅在一起的。例如我们希望把计数器结果显示在标签上&…...

一百三十八、ClickHouse——使用clickhouse-backup备份ClickHouse库表

一、目标 使用clickhouse-backup在本地全库备份ClickHouse的数据库 二、前提 已经安装好clickhouse-backup 注意&#xff1a;由于之前同事已经按照好clickhouse-backup&#xff0c;所以我就没有安装 如有需要请参考其他人的博客安装一下&#xff0c;下面是我认为比较好的一…...

【无标题】使用Debate Dynamics在知识图谱上进行推理(2020)7.31

使用Debate Dynamics在知识图谱上进行推理 摘要介绍背景与相关工作我们的方法 摘要 我们提出了一种新的基于 Debate Dynamics 的知识图谱自动推理方法。 其主要思想是将三重分类任务定义为两个强化学习主体之间的辩论游戏&#xff0c;这两个主体提取论点&#xff08;知识图中…...

windows下若依vue项目部署

下载若依项目&#xff0c;前端后端项目本地启动前端打包&#xff0c;后端打包配置nginx.conf 需要注意的是&#xff1a;路径别用中文&#xff0c;要不然报错 #前台访问地址及端口80&#xff0c;在vue.config.js中可查看server {listen 80;server_name localhost; #后台…...

【目标检测】基于yolov5的水下垃圾检测(附代码和数据集,7684张图片)

写在前面: 首先感谢兄弟们的订阅,让我有创作的动力,在创作过程我会尽最大能力,保证作品的质量,如果有问题,可以私信我,让我们携手共进,共创辉煌。 路虽远,行则将至;事虽难,做则必成。只要有愚公移山的志气、滴水穿石的毅力,脚踏实地,埋头苦干,积跬步以至千里,就…...

P1734 最大约数和

题目描述 选取和不超过 S 的若干个不同的正整数&#xff0c;使得所有数的约数&#xff08;不含它本身&#xff09;之和最大。 输入格式 输入一个正整数 S。 输出格式 输出最大的约数之和。 输入输出样例 输入 11 输出 9 说明/提示 【样例说明】 取数字 4 和 6&a…...

Excel将单元格中的json本文格式化

打开Excel文件并按下ALT F11打开Visual Basic for Applications&#xff08;VBA&#xff09;编辑器。 输入下面的代码 Sub FormatJSONCells()Dim cell As RangeDim jsonString As StringDim json As ObjectDim formattedJSON As String 循环遍历选定的单元格范围For Each ce…...

Baumer工业相机堡盟工业相机如何通过BGAPI SDK获取相机当前实时帧率(C#)

Baumer工业相机堡盟工业相机如何通过BGAPISDK里函数来计算相机的实时帧率&#xff08;C#&#xff09; Baumer工业相机Baumer工业相机的帧率的技术背景Baumer工业相机的帧率获取方式CameraExplorer如何查看相机帧率信息在BGAPI SDK里通过函数获取相机帧率 Baumer工业相机通过BGA…...

XGBoost的基础思想与实现

目录 1. XGBoost VS 梯度提升树 1.1 XGBoost实现精确性与复杂度之间的平衡 1.2 XGBoost极大程度地降低模型复杂度、提升模型运行效率 1.3 保留了部分与梯度提升树类似的属性 2. XGBoost回归的sklearnAPI实现 2.1 sklearn API 实现回归 2.2 sklearn API 实现分类 3. XGBo…...

【Docker】Docker的服务更新与发现

consul 一、服务注册与发现1. 服务注册与发现的概念2. 服务发现的机制二、consul 的概念1. 什么是 consul2. consul 的特性三、consul 的部署1. consul 服务器架构2. consul 的部署过程2.1 环境配置2.2 consul 服务器建立 Consul 服务查看集群信息通过 http api 获取集群信息2.…...

【Docker 学习笔记】Docker架构及三要素

文章目录 一、Docker 简介二、Docker 架构1. Docker 客户端和服务器2. Docker 架构图3. Docker 运行流程图 三、Docker 三要素1. 镜像&#xff08;Image&#xff09;2. 容器&#xff08;Container&#xff09;3. 仓库&#xff08;Repository&#xff09; 一、Docker 简介 Dock…...

matlab编程实践14、15

目录 数独 "四独"游戏 解的存在和唯一性 算法 常微分方程 数独 采用蛮力试凑法来解决数独问题。&#xff08;采用单选数&#xff0c;以及计算机科学技术中的递推回溯法&#xff09; 以上的数独是图14-2的两个矩阵的和&#xff0c;左侧的矩阵可以由kron和magic函…...

C++ ——STL容器【list】模拟实现

代码仓库&#xff1a; list模拟实现 list源码 数据结构——双向链表 文章目录 &#x1f347;1. 节点结构体&#x1f348;2. list成员&#x1f349;3. 迭代器模板&#x1f34a;4. 迭代器&#x1f34b;5. 插入删除操作&#x1f34c;5.1 insert & erase&#x1f34c;5.2 push_…...

ubuntu 16.04 安装mujoco mujoco_py gym stable_baselines版本问题

ubuntu 16.04系统 Python 3.7.16 mujoco200 (py37mujoco) abc123:~/github/spinningup$ pip list Package Version Editable project location ----------------------------- --------- --------------------------- absl-py …...

自然语言处理(NLP)技术

自然语言处理技术是一种人工智能技术&#xff0c;它的目标是使计算机能够理解、分析、处理和生成自然语言&#xff08;人类使用的语言&#xff09;。NLP技术包括文本分类、情感分析、机器翻译、语音识别、语音合成、信息检索、信息抽取、问答系统等。NLP技术的应用非常广泛&…...

如何将ubuntu LTS升级为Pro

LTS支持周期是5年&#xff1b; Pro支持周期是10年。 Ubuntu Pro专业版笔记 步骤&#xff1a; 打开“软件和更新” 可以看到最右侧的标签是Ubuntu Pro。 在没有升级之前&#xff0c;如果使用下面两步&#xff1a; sudo apt updatesudo apt upgrade 出现如下提示&#xff…...

如何学习ARM嵌入式开发?

ARM和单片机还是有许多区别的&#xff0c;可以说比单片机的应用更为复杂吧&#xff0c;往往在单片机里只需要对一个寄存器赋值就可以的初始化&#xff0c;在ARM下就要调用库函数了。甚至每个引脚其功能都多了许多&#xff0c;相应的配置也会更为麻烦&#xff0c;但如果做多了AR…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

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

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

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...