当前位置: 首页 > 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…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...