每日一题——旋转数组的最小数字
题目
有一个长度为 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 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样的。请问,给定这…...
SpringBoot Jackson 日期格式化统一配置
目录 1.在全局配置文件配置 2.通过JavaBean方式配置 1.在全局配置文件配置 spring:jackson:date-format: yyyy-MM-dd HH:mm:sstime-zone: GMT8 该配置方式仅支持 Date 类型的日期格式化,不支持LocalDate 及 LocalDateTime 的格式化。 2.通过JavaBean方式配置 …...
剑指 Offer 38. 字符串的排列 / LeetCode 47. 全排列 II(回溯法)
题目: 链接:剑指 Offer 38. 字符串的排列 难度:中等 输入一个字符串,打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。 示例: 输入:s “abc” 输出&…...

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

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

【无标题】使用Debate Dynamics在知识图谱上进行推理(2020)7.31
使用Debate Dynamics在知识图谱上进行推理 摘要介绍背景与相关工作我们的方法 摘要 我们提出了一种新的基于 Debate Dynamics 的知识图谱自动推理方法。 其主要思想是将三重分类任务定义为两个强化学习主体之间的辩论游戏,这两个主体提取论点(知识图中…...
windows下若依vue项目部署
下载若依项目,前端后端项目本地启动前端打包,后端打包配置nginx.conf 需要注意的是:路径别用中文,要不然报错 #前台访问地址及端口80,在vue.config.js中可查看server {listen 80;server_name localhost; #后台…...

【目标检测】基于yolov5的水下垃圾检测(附代码和数据集,7684张图片)
写在前面: 首先感谢兄弟们的订阅,让我有创作的动力,在创作过程我会尽最大能力,保证作品的质量,如果有问题,可以私信我,让我们携手共进,共创辉煌。 路虽远,行则将至;事虽难,做则必成。只要有愚公移山的志气、滴水穿石的毅力,脚踏实地,埋头苦干,积跬步以至千里,就…...
P1734 最大约数和
题目描述 选取和不超过 S 的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。 输入格式 输入一个正整数 S。 输出格式 输出最大的约数之和。 输入输出样例 输入 11 输出 9 说明/提示 【样例说明】 取数字 4 和 6&a…...
Excel将单元格中的json本文格式化
打开Excel文件并按下ALT F11打开Visual Basic for Applications(VBA)编辑器。 输入下面的代码 Sub FormatJSONCells()Dim cell As RangeDim jsonString As StringDim json As ObjectDim formattedJSON As String 循环遍历选定的单元格范围For Each ce…...

Baumer工业相机堡盟工业相机如何通过BGAPI SDK获取相机当前实时帧率(C#)
Baumer工业相机堡盟工业相机如何通过BGAPISDK里函数来计算相机的实时帧率(C#) 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. 镜像(Image)2. 容器(Container)3. 仓库(Repository) 一、Docker 简介 Dock…...

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

C++ ——STL容器【list】模拟实现
代码仓库: list模拟实现 list源码 数据结构——双向链表 文章目录 🍇1. 节点结构体🍈2. list成员🍉3. 迭代器模板🍊4. 迭代器🍋5. 插入删除操作🍌5.1 insert & erase🍌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)技术
自然语言处理技术是一种人工智能技术,它的目标是使计算机能够理解、分析、处理和生成自然语言(人类使用的语言)。NLP技术包括文本分类、情感分析、机器翻译、语音识别、语音合成、信息检索、信息抽取、问答系统等。NLP技术的应用非常广泛&…...

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

如何学习ARM嵌入式开发?
ARM和单片机还是有许多区别的,可以说比单片机的应用更为复杂吧,往往在单片机里只需要对一个寄存器赋值就可以的初始化,在ARM下就要调用库函数了。甚至每个引脚其功能都多了许多,相应的配置也会更为麻烦,但如果做多了AR…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...