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

在做题中学习(53): 寻找旋转数组中的最小值

153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode)

解法:O(logn)->很可能就是二分查找

思路:再看看题目要求,可以画出旋转之后数组中元素的大小关系:

首先,数组是具有二段性的(适配二分查找),因为原来的有序数组旋转元素挪到前面后,一定比后面的元素都要大,所以由此可以画出上图。

细节

1.以D为参照 ,判断mid落在[A,B],还是[C,D]区间内,最后如果求出[C,D]区间的左端点,也就是C,就知道了最终结果的下标。

2.以A为参照,那么最后一次旋转的元素变成数组首元素,也就是[A,B]最小的元素,但比[C,D]区间的值都要大,所以也是一种思路。[A,B]区间的值 >A,[C,D]区间的值 <A,其实还是求[C,D]区间的左端点。

3.以A为参照点时,考虑边界情况:旋转后 和 原数组 相同,那么数组首元素 > 尾元素。因为A为参照点时,是以首元素为参照,如果命中 nums[mid] >= sub 条件,则会越过最小元素。

上述两种参照点都可以解决问题,代码也都会给在下方,但注意:

根据在做题中学习(49):排序数组中查找元素的第一个和最后一个位置-CSDN博客

中有更详细的求左区间的讲解和细节问题。

1.以A为参照

class Solution 
{
public:int findMin(vector<int>& nums) {if(nums[0] < nums[nums.size()-1])return nums[0];int left = 0,right = nums.size()-1;int sub = nums[0];while(left < right){int mid = left + (right - left) /2;if(nums[mid] >= sub)left = mid + 1;else if(nums[mid] < sub)right = mid;}        return nums[left];}
};

2.以D为参照

class Solution 
{
public:int findMin(vector<int>& nums) {int left = 0,right = nums.size()-1;int back = right;while(left < right){//求区间左端点int mid = left + (right - left) /2;if(nums[mid] > nums[back])left = mid + 1;else if(nums[mid] <= nums[back])right = mid;}//走到这里,left == rightreturn nums[left];}
};

相关文章:

在做题中学习(53): 寻找旋转数组中的最小值

153. 寻找旋转排序数组中的最小值 - 力扣&#xff08;LeetCode&#xff09; 解法&#xff1a;O(logn)->很可能就是二分查找 思路&#xff1a;再看看题目要求&#xff0c;可以画出旋转之后数组中元素的大小关系&#xff1a; 首先&#xff0c;数组是具有二段性的(适配二分查…...

C#语言进阶(三) 元组

总目录 C# 语法总目录 元组目录 元组1. 元组元素命名2. 元组的解构3. 元组的比较 元组 元组(tuple)是一组存储值的便捷方式。 元组的目的主要是&#xff0c;不使用out参数而从方法中返回多个值。(匿名类型无法做这个操作)元组能做匿名类型所有操作。 元组是值类型&#xff0…...

实用的Chrome 浏览器命令

Google Chrome 浏览器提供了许多快捷命令和实用功能&#xff0c;可以帮助用户提高效率和改善浏览体验。这里列举了一些非常实用的Chrome浏览器命令&#xff1a; 1. **CtrlT** / **CmdT** - 打开一个新的标签页。 2. **CtrlShiftT** / **CmdShiftT** - 重新打开最后关闭的标签页…...

IDEA远程连接docker服务,windows版docker desktop

1.windows上安装docker desktop docker desktop下载地址&#xff1a;Docker Desktop: The #1 Containerization Tool for Developers | Docker 有的windows系统不支持安装docker desktop 安装完之后我们可以直接打开&#xff0c;可以选择不登录使用 我们用IDEA连接到docker …...

Rust 和 Go 哪个更好?

在讨论 Rust 与 Go 两种编程语言哪种更优秀时&#xff0c;我们将探讨它们在性能、简易性、安全性、功能、规模和并发处理等方面的比较。同时&#xff0c;我们看看它们有什么共同点和根本的差异。现在就来看看这个友好而公平的对比。 Rust 和 Go 都是优秀的选择 首先&#xff…...

【免费Java系列】大家好 ,今天是学习面向对象高级的第八天点赞收藏关注,持续更新作品 !

这是java进阶课面向对象第一天的课程可以坐传送去学习http://t.csdnimg.cn/Lq3io day08-Map集合、Stream流、File类 一、Map集合 同学们&#xff0c;在前面几节课我们已经学习了Map集合的常用方法&#xff0c;以及遍历方式。 下面我们要学习的是Map接口下面的是三个实现类H…...

RPC 失败。curl 16 Error in the HTTP2 framing layer

报错&#xff1a; (base) hh-virtual-machine:~/work$ git clone https://github.com/yangzongzhuan/RuoYi-Vue3.git 正克隆到 RuoYi-Vue3... error: RPC 失败。curl 16 Error in the HTTP2 framing layer fatal: 在引用列表之后应该有一个 flush 包这个错误通常是由于 Git 在…...

(图论)最短路问题合集(包含C,C++,Java,Python,Go)

不存在负权边&#xff1a; 1.朴素dijkstra算法 原题&#xff1a; 思路&#xff1a;&#xff08;依然是贪心的思想&#xff09; 1.初始化距离&#xff1a;dis[1]0&#xff0c;dis[i]INF&#xff08;正无穷&#xff09; 2.循环n次&#xff1a; 找到当前不在s中的dis最小的点&…...

电脑文件批量重命名不求人:快速操作,高效技巧让你轻松搞定

在数字化时代&#xff0c;电脑文件的管理与整理显得尤为重要。当面对大量需要重命名的文件时&#xff0c;一个个手动修改不仅耗时&#xff0c;还容易出错。那么&#xff0c;有没有一种方法可以快速、高效地完成这一任务呢&#xff1f;答案是肯定的&#xff0c;下面就来介绍几种…...

基于springboot的网上点餐系统源码数据库

基于springboot的网上点餐系统源码数据库 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff1b;对于网上点餐系统当然也不能排除在外&#xff0c;随着网络技术的不断成熟&#xff0c;带动了网上点餐系统…...

mysql cluster数据库集群介绍、部署及配置

前言: MySQL集群是一个无共享的、分布式节点架构的存储方案,旨在提供容错性和高性能。它由三个主要节点组成:管理节点(MGM)、数据节点和SQL节点。 管理节点(MGM) 定义与用途:管理节点是MySQL Cluster的控制中心,负责管理集群内的其他节点。它提供配置数据,启动和停止…...

uniapp的app端软件更新弹框

1&#xff1a;使用html PLUS实现&#xff1a;地址HTML5 API Reference (html5plus.org)&#xff0c;效果图 2&#xff1a;在app.vue的onLaunch生命周期中&#xff0c;代码如下&#xff1a; onLaunch: function() {let a 0let view new plus.nativeObj.View(maskView, {backg…...

win11 Terminal 部分窗口美化

需求及分析&#xff1a;因为在 cmd、anaconda prompt 窗口中输入命令较多&#xff0c;而命令输入行和输出结果都是同一个颜色&#xff0c;不易阅读&#xff0c;故将需求定性为「美化窗口」。 美化结束后&#xff0c;我在想是否能不安装任何软件&#xff0c;简单地通过调整主题颜…...

开源go实现的iot物联网新基建平台

软件介绍 Magistrala IoT平台是由Abstract Machines公司开发的创新基础设施解决方案&#xff0c;旨在帮助组织和开发者构建安全、可扩展和创新的物联网应用程序。曾经被称为Mainflux的平台&#xff0c;现在已经开源&#xff0c;并在国际物联网领域受到广泛关注。 功能描述 多协…...

24深圳杯ABCD成品论文47页+各小问代码+图表

A题多个火箭残骸的准确定位&#xff1a; A题已经更新完22页完整版论文&#xff0b;高清无水印照片&#xff0b;Python&#xff08;MATLAB&#xff09;代码简单麦麦https://www.jdmm.cc/file/2710544/ 问题1&#xff1a;单个残骸的音爆位置确定 建模思路&#xff1a; 1. 声波传…...

doris经典bug

在部署完登录web页面查看的时候会发现只有一个节点可以读取信息剩余的节点什么也没读取到 在发现问题后&#xff0c;我们去对应的节点去看log日志&#xff0c;发现它自己绑定到前端的地址上了 现在我们已经发现问题了&#xff0c;以下就开始解决问题 重置doris 首先对be进行操…...

贪心算法应用例题

最优装载问题 #include <stdio.h> #include <algorithm>//排序int main() {int data[] { 8,20,5,80,3,420,14,330,70 };//物体重量int max 500;//船容最大总重量int count sizeof(data) / sizeof(data[0]);//物体数量std::sort(data, data count);//排序,排完数…...

亚信科技精彩亮相2024中国移动算力网络大会,数智创新共筑“新质生产力”

4月28至29日&#xff0c;江苏省人民政府指导、中国移动通信集团有限公司主办的2024中国移动算力网络大会在苏州举办。大会以“算力网络点亮AI时代”为主题&#xff0c;旨在凝聚生态伙伴合力&#xff0c;共同探索算力网络、云计算等数智能力空间&#xff0c;共促我国算网产业和数…...

图像处理中的颜色空间转换

在图像处理中&#xff0c;颜色空间转换是指将图像从一种颜色表示方式转换为另一种颜色表示方式。常见的颜色空间转换包括RGB到HSV、RGB到灰度、RGB到CMYK等。 RGB到HSV转换&#xff1a; RGB颜色空间由红色&#xff08;R&#xff09;、绿色&#xff08;G&#xff09;和蓝色&…...

网络安全之静态路由

以下是一个静态路由的拓扑图 Aping通B&#xff0c;C可以ping通D。 路由器转发数据需要路由表&#xff0c;但仍可以Aping通B&#xff0c;C可以ping通D&#xff0c;是因为产生了直连路由&#xff1a;产生的条件有两个&#xff0c;接口有IP&#xff0c;接口双up(物理up&#xff…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...