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

「优选算法刷题」:寻找旋转排序数组中的最小值

一、题目

已知一个长度为 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 的数组&#xff0c;预先按照升序排列&#xff0c;经由 1 到 n 次 旋转 后&#xff0c;得到输入数组。例如&#xff0c;原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到&#xff1a; 若旋转 4 次&#xff0c;则可以得到 [4,5,6,7,0,1,2]若旋转 7 次…...

MySQL 基础入门指南:从安装到基本操作

一、简介 MySQL 是一种流行的开源关系型数据库管理系统&#xff0c;被广泛用于各种规模和类型的应用程序中。如果您对 MySQL 还不熟悉&#xff0c;本文将为您提供一个基础的入门指南&#xff0c;从安装到基本操作。 1.1 安装 MySQL 首先&#xff0c;您需要下载并安装 MySQL。…...

嵌入式Qt Qt Creator安装与工程介绍

一.Qt概述 什么是Qt&#xff1a;Qt是一个跨平台的C图形用户界面应用程序框架。它为应用程序开发者提供建立图形界面所需的所有功能。它是完全面向对象的&#xff0c;很容易扩展&#xff0c;并且允许真正的组件编程。 二.Qt Creator下载安装 下载地址&#xff1a;Index of /a…...

Windows 系统盘(C盘)爆红如何清理、如何增加C盘空间

1、简介 Windows系统中&#xff0c;系统和保留占用太多的空间&#xff0c;一旦系统盘分配空间较少&#xff0c;使用一段时间后&#xff0c;备份文件、临时文件、系统更新记录等都会在占用系统盘较大空间&#xff0c;导致系统盘空间不够使用&#xff0c;会造成应用运行卡顿。如何…...

【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打法

天命&#xff1a;我发现题题不一样&#xff0c;已知跟求知的需求都不一样 题目一&#xff1a;已知 p q E &#xff0c;计算T&#xff0c;最后求D 已知两个质数p q 和 公钥E &#xff0c;通过p和q计算出欧拉函数T&#xff0c;最后求私钥D 【密码学 | CTF】BUUCTF RSA-CSDN…...

红衣大叔讲AI:从OpenAI发布首个视频大模型Sora,谈2024年视觉大模型的十大趋势

OpenAI宣布推出全新的生成式人工智能模型“Sora”。据了解&#xff0c;通过文本指令&#xff0c;Sora可以直接输出长达60秒的视频&#xff0c;并且包含高度细致的背景、复杂的多角度镜头&#xff0c;以及富有情感的多个角色。 OpenAI发布首个视频大模型Sora&#xff0c;一句话生…...

java远程连接Linux执行命令的三种方式

java远程连接Linux执行命令的三种方式 1. 使用JDK自带的RunTime类和Process类实现2. ganymed-ssh2 实现3. jsch实现4. 完整代码&#xff1a;执行shell命令下载和上传文件 1. 使用JDK自带的RunTime类和Process类实现 public static void main(String[] args){Process proc Run…...

JavaScript- let var const区别

let 允许你声明⼀个作⽤域被限制在块级中的变量、语句或者表达式 let 绑定不受变量提升的约束&#xff0c;这意味着 let 声明不会被提升到当前 该变量处于从块开始到初始化处理的“暂存死区” function example() {let x 10;if (true) {let x 20;console.log(x); // Outpu…...

指针的经典笔试题

经典的指针试题&#xff0c;让你彻底理解指针 前言 之前对于指针做了一个详解&#xff0c;现在来看一些关于指针的经典面试题。 再次说一下数组名 数组名通常表示的都是首元素的地址&#xff0c;但是有两个意外&#xff0c;1.sizeof&#xff08;数组名&#xff09;这里数组名…...

书生浦语大模型实战营-课程笔记(1)

模型应用过程&#xff0c;大致还是了解的。和之前实习做CV项目的时候比起来&#xff0c;多了智能体这个环节。智能体是个啥&#xff1f; 类似上张图&#xff0c;智能体不太清楚。感觉是偏应用而不是模型的东西&#xff1f; 数据集类型很多&#xff0c;有文本/图片/视频。所以…...

磁盘database数据恢复: ddrescue,dd和Android 设备的数据拷贝

ddrescue和dd 区别&#xff1a; GNU ddrescue 不是 dd 的衍生物&#xff0c;也与 dd 没有任何关系 除了两者都可用于将数据从一台设备复制到另一台设备。 关键的区别在于 ddrescue 使用复杂的算法来复制 来自故障驱动器的数据&#xff0c;尽可能少地造成额外的损坏。ddrescue…...

SpringMVC-入门

1.概念 SpringMVC是一种软件架构思想&#xff0c;把软件按照模型(Model)、视图(View)、控制器(Controller)这三层来划分。Model&#xff1a;指的是工程中JavaBean&#xff0c;用来处理数据View&#xff1a;指的是工程中的html、jsp等页面&#xff0c;用来展示给用户数据Control…...

需要学习的知识点清单

div 4 div 3 F :拓扑排序 G : 组合数学 D : 结构体排序 div 2 div 12...

杂谈--spconv导出中onnx的扩展阅读

Onnx 使用 Onnx 介绍 Onnx (Open Neural Network Exchange) 的本质是一种 Protobuf 格式文件&#xff0c;通常看到的 .onnx 文件其实就是通过 Protobuf 序列化储存的文件。onnx-ml.proto 通过 protoc (Protobuf 提供的编译程序) 编译得到 onnx-ml.pb.h 和 onnx-ml.pb.cc 或 on…...

嵌入式培训机构四个月实训课程笔记(完整版)-Linux ARM驱动编程第二天-arm ads下的start.S分析(物联技术666)

链接&#xff1a;https://pan.baidu.com/s/1E4x2TX_9SYhxM9sWfnehMg?pwd1688 提取码&#xff1a;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

这一部分主要来梳理二叉树题目最简单最基础的部分&#xff0c;包括遍历&#xff0c;一些简单题目。 一、Leecode 144 - 二叉树的前序遍历 https://leetcode.cn/problems/binary-tree-preorder-traversal/description/ 二叉树的遍历是入门。我们需要在程序一开始就创建一个空…...

tcp 中使用的定时器

定时器的使用场景主要有两种。 &#xff08;1&#xff09;周期性任务 这是定时器最常用的一种场景&#xff0c;比如 tcp 中的 keepalive 定时器&#xff0c;起到 tcp 连接的两端保活的作用&#xff0c;周期性发送数据包&#xff0c;如果对端回复报文&#xff0c;说明对端还活着…...

黑马Java——IO流

一、IO流的概述 IO流&#xff1a;存储和读取数据的解决方案 IO流和File是息息相关的 1、IO流的分类 1.1、纯文本文件 word、Excel不是纯文本文件 而txt或者md文件是纯文本文件 2、小结 二、IO流的体系结构 三、字节流 1、FileOutputStream&#xff08;字节输出流&#xff…...

基于YOLOv11深度学习的花卉识别检测系统(YOLOv11+YOLO数据集+UI界面+登录注册界面+Python项目源码+模型)

一、项目介绍 花卉识别是计算机视觉在植物学领域的重要应用方向&#xff0c;对于植物分类研究、生态保护、园林管理等领域具有重要意义。然而&#xff0c;由于花卉种类繁多、形态各异&#xff0c;且受光照、角度、遮挡等因素影响&#xff0c;传统方法难以实现高效准确的识别。…...

FPGA新手必看:Vivado 2023.1里用DDS IP核生成1MHz正弦波,附完整仿真代码

FPGA实战&#xff1a;从零构建1MHz正弦波生成器的Vivado全流程解析 刚拿到FPGA开发板时&#xff0c;我最想实现的第一个项目就是信号发生器。看着示波器上跳动的波形从自己编写的代码中产生&#xff0c;这种成就感无可替代。本文将带你用Xilinx Vivado 2023.1中的DDS IP核&…...

手把手教你用Qt6和Arduino Uno打造实时数据监控面板(附串口数据粘包处理源码)

基于Qt6与Arduino Uno的工业级数据可视化系统开发实战 在工业物联网和智能硬件开发领域&#xff0c;实时数据监控是核心需求之一。想象一下这样的场景&#xff1a;车间里的温度传感器阵列通过Arduino采集数据&#xff0c;工程师在办公室的PC端就能实时查看温度曲线波动&#x…...

从ThreadLocal到TransmittableThreadLocal:手把手解决线程池上下文传递难题

从ThreadLocal到TransmittableThreadLocal&#xff1a;线程池上下文传递的终极解决方案 在分布式系统和微服务架构盛行的今天&#xff0c;异步编程已成为Java开发者日常工作中不可或缺的一部分。无论是处理高并发请求、优化系统性能&#xff0c;还是实现复杂的业务流程&#xf…...

Wan2.2-I2V-A14B实战案例:为本地餐饮店生成15秒抖音爆款菜品视频

Wan2.2-I2V-A14B实战案例&#xff1a;为本地餐饮店生成15秒抖音爆款菜品视频 1. 项目背景与价值 对于本地餐饮商家来说&#xff0c;短视频营销已经成为吸引顾客的重要手段。然而&#xff0c;专业视频制作成本高、周期长&#xff0c;很多小店难以承担。Wan2.2-I2V-A14B文生视频…...

Qwen-Image镜像实战:基于RTX4090D,轻松实现图片问答与内容分析

Qwen-Image镜像实战&#xff1a;基于RTX4090D&#xff0c;轻松实现图片问答与内容分析 1. 引言&#xff1a;Qwen-Image镜像的核心价值 在当今多模态AI技术快速发展的背景下&#xff0c;能够同时理解图像和文本的视觉语言模型正变得越来越重要。Qwen-Image作为通义千问系列中的…...

深入解析cufftPlanMany:从参数配置到高效FFT实现

1. 为什么需要cufftPlanMany&#xff1f; 第一次接触CUDA FFT时&#xff0c;很多人都是从cufftPlan1d、cufftPlan2d这些基础接口开始的。但当你真正处理实际工程问题时&#xff0c;会发现这些简单接口远远不够用。比如要处理批量信号、非连续内存数据、子区域FFT计算等场景时&a…...

别再手动点啦!用Android无障碍服务+讯飞语音,5分钟实现App语音操控(保姆级教程)

用Android无障碍服务打造语音操控神器&#xff1a;5分钟实现"可见即可说" 你是否厌倦了在手机上反复点击屏幕的操作&#xff1f;想象一下&#xff0c;只需对着手机说出"打开微信"、"点击朋友圈"、"返回主页"&#xff0c;设备就能自动完…...

收藏!阿里后端转大模型应用层,2年Agent/RAG经验,斩获字节30%涨幅offer|小白程序员必看学习路径

作为一名从传统后端开发起步的程序员&#xff0c;我毕业后顺利入职阿里&#xff0c;做了一年后端开发工作后&#xff0c;敏锐捕捉到大模型应用层的爆发趋势&#xff0c;果断转型深耕。经过两年的Agent、RAG相关开发实践&#xff0c;最终成功拿到字节跳动Agent开发岗位offer&…...

如何用Obsidian Image Converter实现图像高效管理?超实用技巧分享

如何用Obsidian Image Converter实现图像高效管理&#xff1f;超实用技巧分享 【免费下载链接】obsidian-image-converter ⚡️ Convert, compress, resize, annotate, markup, draw, crop, rotate, flip, align images directly in Obsidian. Drag-resize, rename with variab…...