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

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

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…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...