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

每日一题——寻找旋转排序数组中的最小值(I)

寻找旋转排序数组中的最小值——I

题目链接

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DJE729nA-1691849612603)(C:\Users\HUASHUO\AppData\Roaming\Typora\typora-user-images\image-20230812212433885.png)]


思路

首先我们以数组[1,2,3,4,5,6,7]举个例子,经过旋转后它无非就这两种情况

情况一:旋转过后数组变成两段有序数列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-T0xFO4EO-1691849612604)(C:\Users\HUASHUO\AppData\Roaming\Typora\typora-user-images\image-20230812214608839.png)]

情况二:旋转过后数组不变,仍然有序

而这两种情况都有一个共性

以数组**最右边的值val**为研究对象,最小值1右边的所有数必定小于val;最小值左边的数必定大于val

我们可以画出如下的折线图来总结:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5Rc8KcUx-1691849612604)(C:\Users\HUASHUO\AppData\Roaming\Typora\typora-user-images\image-20230812220235167.png)]

知道了这些后,我们就可以利用二分法求解了:

  • 我们设左边界为left,右边界为right,左右边界的中间值为mid
  • 由上面的分析可以知道,若nums[mid] > nums[right],就说明最小值一定在中间值的右侧,中间值左侧的区域直接舍弃即可:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BqDwQvNv-1691849612604)(C:\Users\HUASHUO\AppData\Roaming\Typora\typora-user-images\image-20230812220508295.png)]

  • nums[mid] < nums[right],就说明最小值一定在中间值的左侧或者就是中间值,中间值右侧的区域直接舍弃即可:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P8eu1wOe-1691849612604)(C:\Users\HUASHUO\AppData\Roaming\Typora\typora-user-images\image-20230812220756078.png)]

  • 随着区间的不断缩小,leftright最终就会相等,其最后停留的位置也就是数组的最小值

实现代码

int findMin(int* nums, int numsSize) {int left = 0;int right = numsSize - 1;while (left < right){int mid = (right - left) / 2 + left;//如果中间值大于最右边的值,那么最小值一定在中间值的右边if (nums[mid] > nums[right])left = mid + 1;//否则,最小值就在最右边的值的左边,也可能就是这个中间值elseright = mid;}//循环结束时,left和right所在的位置就是最小值的位置return nums[left];
}

相关文章:

每日一题——寻找旋转排序数组中的最小值(I)

寻找旋转排序数组中的最小值——I 题目链接 思路 首先我们以数组[1,2,3,4,5,6,7]举个例子&#xff0c;经过旋转后它无非就这两种情况&#xff1a; 情况一&#xff1a;旋转过后数组变成两段有序数列&#xff1a; 情况二&#xff1a;旋转过后数组不变&#xff0c;仍然有序&…...

C语言每日一题:16:数对。

思路一&#xff1a;基本思路 1.x,y均不大于n&#xff0c;就是小于等于n。 2.x%y大于等于k。 3.一般的思路使用双for循环去遍历每一对数。 代码实现&#xff1a; #include <stdio.h> int main() {int n 0;int k 0;//输入scanf("%d%d", &n, &k);int x…...

中科亿海微浮点数转换定点数

引言 浮点数转换定点数是一种常见的数值转换技术&#xff0c;用于将浮点数表示转换为定点数表示。浮点数表示采用指数和尾数的形式&#xff0c;可以表示较大范围的数值&#xff0c;但存在精度有限的问题。而定点数表示则采用固定小数点位置的形式&#xff0c;具有固定的精度和范…...

JavaScript激活严格模式

在JavaScript中&#xff0c;严格模式是一种特殊的模式&#xff0c;通过’use strict’;去激活严格模式&#xff01;在 JavaScript 中&#xff0c;“use strict” 是一种指令&#xff0c;表示在代码运行时启用严格模式&#xff0c;从而禁止使用一些不安全或者不规范的语法&#…...

Linux cond_resched()简介

文章目录 简介一、cond_resched1.1 _cond_resched1.2 should_resched1.2.1 __preempt_count&#xff1a;1.2.2 函数说明 1.3 preempt_schedule_common1.3.1 preempt_schedule_common1.3.2 preempt_latency_start/stop 1.3.3 preempt_disable_notrace 参考资料 简介 Linux 内核…...

初出茅庐的小李博客之认识编码器

编码器是什么&#xff1a; 一种将角位移或者角速度转换成一连串电数字脉冲的旋转式传感器&#xff0c;我们可以通过编码器测量到底位移或者速度信息。编码器通常由一个旋转部分和一个固定部分组成&#xff0c;旋转部分随着被测量的物体进行旋转&#xff0c;固定部分则保持不动…...

NVIDIA TX2 NX编译及更新设备树

在NVIDIA官网下载相关文件 官网网址:https://developer.nvidia.com/embedded/jetson-linux-archive 我选择的版本为R32.7.4 需要下载3个文件,BSP、根文件系统、BSP源码: 解压 将Tegra_Linux_Sample-Root-Filesystem_R32.7.4_aarch64文件夹下的内容提取到Jetson_Linux_R32.…...

从零开始学Python(二)运算符、if、循环结构

&#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于Python的相关操作吧 目录 &#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 一.运算符 1.基本运算符 2.比较运算符 …...

Sentinel整合Spring Cloud Gateway、Zuul详解

Sentinel 支持对 Spring Cloud Gateway、Zuul 等主流的 API Gateway 进行限流。 Sentinel 1.6.0 引入了 Sentinel API Gateway Adapter Common 模块&#xff0c;此模块中包含网关限流的规则和自定义 API 的实体和管理逻辑&#xff1a; GatewayFlowRule&#xff1a;网关限流规则…...

wsl2安装mysql环境

安装完mysql后通过如下命令启动mysql service mysql start 会显示如下错误&#xff1a; mysql: unrecognized service 实际上上面显示的错误是由于mysql没有启动成功造成的 我们要想办法成功启动mysql才可以 1.通过如下操作就可以跳过密码直接进入mysql环境 2.如果想找到my…...

C#质检工具(StyleCop、SonarLint)

1、StyleCop StyleCop工具主要类似java中的checkStyle,是检查代码样式规范的工具。 1.1、StyleCop安装流程: 图1.1 图1.2 图1.3 安装StyleCop插件时可能会遇到下载特慢或卡住不动的情况,需注意: 1)网上说的关闭IPV6功能不管用 2)网上说的自动指定dns不管用 3)网上…...

PyTorch翻译官网教程-NLP FROM SCRATCH: GENERATING NAMES WITH A CHARACTER-LEVEL RNN

官网链接 NLP From Scratch: Generating Names with a Character-Level RNN — PyTorch Tutorials 2.0.1cu117 documentation 使用字符级RNN生成名字 这是我们关于“NLP From Scratch”的三篇教程中的第二篇。在第一个教程中</intermediate/char_rnn_classification_tutor…...

【C语言】结构体详解

现实生活中一个事物&#xff0c;会有许多属性连接起来。而C语言引入一种构造数据类型——结构体 将属于一个事物的多个数据组织起来以体现其内部联系。 一、结构体类型的定义 结构体类型 是一种 构造类型&#xff0c;它是由若干成员组成的&#xff0c;每个成员可以是一个基本…...

leetcode242. 有效的字母异位词

题目&#xff1a;leetcode242. 有效的字母异位词 描述&#xff1a; 给定两个字符串 s 和 t &#xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。 注意&#xff1a;若 s 和 t 中每个字符出现的次数都相同&#xff0c;则称 s 和 t 互为字母异位词。 示例 1: 输入: s “…...

Unity 编辑器资源导入处理函数 OnPostprocessAudio :深入解析与实用案例

Unity 编辑器资源导入处理函数 OnPostprocessAudio 用法 点击封面跳转下载页面 简介 在Unity中&#xff0c;我们可以使用编辑器资源导入处理函数&#xff08;OnPostprocessAudio&#xff09;来自定义处理音频资源的导入过程。这个函数是继承自AssetPostprocessor类的&#xff…...

uniapp开发(由浅到深)

文章目录 1. 项目构建1.1 脚手架构建1.2 HBuilderX创建 uni-app项目步骤&#xff1a; 2 . 包依赖2.1 uView2.2 使用uni原生ui插件2.3 uni-modules2.4 vuex使用 3.跨平台兼容3.1 条件编译 4.API 使用4.1 正逆参数传递 5. 接口封装6. 多端打包3.1 微信小程序3.2 打包App3.2.1 自有…...

QT-基于Buildroot构建系统镜像下实现QT开发

QT-基于Buildroot构建系统镜像下实现QT开发 BuildRootUboot的仓库地址和commit idKernel 的仓库地址和commit id BuildRoot已编译库在Windows上的Create上创建项目编译QT项目 BuildRoot 这部分按照100ask官网的教程走即可: Uboot的仓库地址和commit id https://e.coding.net/…...

优雅地处理RabbitMQ中的消息丢失

目录 一、异常处理 二、消息重试机制 三、错误日志记录 四、死信队列 五、监控与告警 优雅地处理RabbitMQ中的消息丢失对于构建可靠的消息系统至关重要。下面将介绍一些优雅处理消息丢失的方案&#xff0c;包括异常处理、重试机制、错误日志记录、死信队列和监控告警等。…...

Vim入门教程vimtutor1.7总结

vimtutor命令可以打开教程文档 原文特别提示 ⬇⬇⬇ 特别提示&#xff1a;切记您要在使用中学习&#xff0c;而不是在记忆中学习 Vim模式 正常模式&#xff08;Normal Mode&#xff09;&#xff1a;默认模式&#xff0c;可以使用基础命令进行操作命令模式&#xff08;Command…...

Stephen Wolfram:让 ChatGPT 真正起作用的是什么?

What Really Lets ChatGPT Work? 让 ChatGPT 真正起作用的是什么&#xff1f; Human language—and the processes of thinking involved in generating it—have always seemed to represent a kind of pinnacle of complexity. And indeed it’s seemed somewhat remarkabl…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...