「优选算法刷题」:寻找旋转排序数组中的最小值
一、题目
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
- 若旋转
4次,则可以得到[4,5,6,7,0,1,2] - 若旋转
7次,则可以得到[0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1:
输入:nums = [3,4,5,1,2] 输出:1 解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
示例 2:
输入:nums = [4,5,6,7,0,1,2] 输出:0 解释:原数组为 [0,1,2,4,5,6,7] ,旋转 3 次得到输入数组。
示例 3:
输入:nums = [11,13,15,17] 输出:11 解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。
二、思路解析
观察一下题目所给的数据,比如示例 1 ,我们可以发现下标为 3 的元素 1 跟其他元素有所不同:

而这就是一个二段性,使得查找区间能够⼀分为二,也是二分查找的本质。

而这个二段性还可以继续抽象成上图,其中 C 点就是我们要求的点。
因此,初始化左右两个指针 left , right :
然后根据 mid 的落点,我们可以这样划分下⼀次查询的区间:
▪ 当 mid 在 [A,B] 区间的时候,也就是 mid 位置的值严格大于 D 点的值,下⼀次查询区间在 [mid + 1,right] 上;
▪ 当 mid 在 [C,D] 区间的时候,也就是 mid 位置的值严格小于等于 D 点的值,下次查询区间在[left,mid] 上。
当区间长度变成 1 的时候,就是我们要找的结果。
具体实现请看下面代码👇
三、完整代码
class Solution {public int findMin(int[] nums) {int left = 0;int right = nums.length - 1;int x = nums[right];while(left < right){int mid = left + (right - left - 1) / 2;if(x < nums[mid]){left = mid + 1;}else{right = mid;}}return nums[left];}
}
以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!
相关文章:
「优选算法刷题」:寻找旋转排序数组中的最小值
一、题目 已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到: 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]若旋转 7 次…...
MySQL 基础入门指南:从安装到基本操作
一、简介 MySQL 是一种流行的开源关系型数据库管理系统,被广泛用于各种规模和类型的应用程序中。如果您对 MySQL 还不熟悉,本文将为您提供一个基础的入门指南,从安装到基本操作。 1.1 安装 MySQL 首先,您需要下载并安装 MySQL。…...
嵌入式Qt Qt Creator安装与工程介绍
一.Qt概述 什么是Qt:Qt是一个跨平台的C图形用户界面应用程序框架。它为应用程序开发者提供建立图形界面所需的所有功能。它是完全面向对象的,很容易扩展,并且允许真正的组件编程。 二.Qt Creator下载安装 下载地址:Index of /a…...
Windows 系统盘(C盘)爆红如何清理、如何增加C盘空间
1、简介 Windows系统中,系统和保留占用太多的空间,一旦系统盘分配空间较少,使用一段时间后,备份文件、临时文件、系统更新记录等都会在占用系统盘较大空间,导致系统盘空间不够使用,会造成应用运行卡顿。如何…...
【JavaEE Spring】Spring 原理
Spring 原理 1. Bean的作⽤域1.1 概念1.2 Bean的作⽤域 2. Bean的⽣命周期 1. Bean的作⽤域 1.1 概念 在Spring IoC&DI阶段, 我们学习了Spring是如何帮助我们管理对象的. 通过 Controller , Service , Repository , Component , Configuration ,Bean 来声明Bean对象。通…...
【Crypto | CTF】RSA打法
天命:我发现题题不一样,已知跟求知的需求都不一样 题目一:已知 p q E ,计算T,最后求D 已知两个质数p q 和 公钥E ,通过p和q计算出欧拉函数T,最后求私钥D 【密码学 | CTF】BUUCTF RSA-CSDN…...
红衣大叔讲AI:从OpenAI发布首个视频大模型Sora,谈2024年视觉大模型的十大趋势
OpenAI宣布推出全新的生成式人工智能模型“Sora”。据了解,通过文本指令,Sora可以直接输出长达60秒的视频,并且包含高度细致的背景、复杂的多角度镜头,以及富有情感的多个角色。 OpenAI发布首个视频大模型Sora,一句话生…...
java远程连接Linux执行命令的三种方式
java远程连接Linux执行命令的三种方式 1. 使用JDK自带的RunTime类和Process类实现2. ganymed-ssh2 实现3. jsch实现4. 完整代码:执行shell命令下载和上传文件 1. 使用JDK自带的RunTime类和Process类实现 public static void main(String[] args){Process proc Run…...
JavaScript- let var const区别
let 允许你声明⼀个作⽤域被限制在块级中的变量、语句或者表达式 let 绑定不受变量提升的约束,这意味着 let 声明不会被提升到当前 该变量处于从块开始到初始化处理的“暂存死区” function example() {let x 10;if (true) {let x 20;console.log(x); // Outpu…...
指针的经典笔试题
经典的指针试题,让你彻底理解指针 前言 之前对于指针做了一个详解,现在来看一些关于指针的经典面试题。 再次说一下数组名 数组名通常表示的都是首元素的地址,但是有两个意外,1.sizeof(数组名)这里数组名…...
书生浦语大模型实战营-课程笔记(1)
模型应用过程,大致还是了解的。和之前实习做CV项目的时候比起来,多了智能体这个环节。智能体是个啥? 类似上张图,智能体不太清楚。感觉是偏应用而不是模型的东西? 数据集类型很多,有文本/图片/视频。所以…...
磁盘database数据恢复: ddrescue,dd和Android 设备的数据拷贝
ddrescue和dd 区别: GNU ddrescue 不是 dd 的衍生物,也与 dd 没有任何关系 除了两者都可用于将数据从一台设备复制到另一台设备。 关键的区别在于 ddrescue 使用复杂的算法来复制 来自故障驱动器的数据,尽可能少地造成额外的损坏。ddrescue…...
SpringMVC-入门
1.概念 SpringMVC是一种软件架构思想,把软件按照模型(Model)、视图(View)、控制器(Controller)这三层来划分。Model:指的是工程中JavaBean,用来处理数据View:指的是工程中的html、jsp等页面,用来展示给用户数据Control…...
需要学习的知识点清单
div 4 div 3 F :拓扑排序 G : 组合数学 D : 结构体排序 div 2 div 12...
杂谈--spconv导出中onnx的扩展阅读
Onnx 使用 Onnx 介绍 Onnx (Open Neural Network Exchange) 的本质是一种 Protobuf 格式文件,通常看到的 .onnx 文件其实就是通过 Protobuf 序列化储存的文件。onnx-ml.proto 通过 protoc (Protobuf 提供的编译程序) 编译得到 onnx-ml.pb.h 和 onnx-ml.pb.cc 或 on…...
嵌入式培训机构四个月实训课程笔记(完整版)-Linux ARM驱动编程第二天-arm ads下的start.S分析(物联技术666)
链接:https://pan.baidu.com/s/1E4x2TX_9SYhxM9sWfnehMg?pwd1688 提取码:1688 ; ; NAME: 2440INIT.S ; DESC: C start up codes ; Configure memory, ISR ,stacks ; Initialize C-variables ; 完全注释 ; HISTORY: ; 2002.02.25:kwtark: ver 0.…...
STL之list容器的介绍与模拟实现+适配器
STL之list容器的介绍与模拟实现适配器 1. list的介绍2. list容器的使用2.1 list的定义2.2 list iterator的使用2.3 list capacity2.4 list element access2.5 list modifiers2.6 list的迭代器失效 3. list的模拟实现3.1 架构搭建3.2 迭代器3.2.1 正向迭代器3.2.2反向迭代器适配…...
Leetcode With Golang 二叉树 part1
这一部分主要来梳理二叉树题目最简单最基础的部分,包括遍历,一些简单题目。 一、Leecode 144 - 二叉树的前序遍历 https://leetcode.cn/problems/binary-tree-preorder-traversal/description/ 二叉树的遍历是入门。我们需要在程序一开始就创建一个空…...
tcp 中使用的定时器
定时器的使用场景主要有两种。 (1)周期性任务 这是定时器最常用的一种场景,比如 tcp 中的 keepalive 定时器,起到 tcp 连接的两端保活的作用,周期性发送数据包,如果对端回复报文,说明对端还活着…...
黑马Java——IO流
一、IO流的概述 IO流:存储和读取数据的解决方案 IO流和File是息息相关的 1、IO流的分类 1.1、纯文本文件 word、Excel不是纯文本文件 而txt或者md文件是纯文本文件 2、小结 二、IO流的体系结构 三、字节流 1、FileOutputStream(字节输出流ÿ…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
