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

【每日一题】154. 寻找旋转排序数组中的最小值 II

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

已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到:

  • 若旋转 4 次,则可以得到 [4,5,6,7,0,1,4]
  • 若旋转 7 次,则可以得到 [0,1,4,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 ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须尽可能减少整个过程的操作步骤。

示例 1:

输入:nums = [1,3,5]
输出:1

示例 2:

输入:nums = [2,2,2,0,1]
输出:0

提示:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 原来是一个升序排序的数组,并进行了 1 至 n 次旋转
class Solution {public int findMin(int[] nums) {//暴力解题// int len = nums.length;// int ans = nums[0];// for(int i = 1 ;i < len ; i++) {//     if(nums[i] < ans) {//         ans = nums[i];//     }// }// return ans;int left = 0;int right = nums.length - 1;while(left < right) {int mid = (left+right) / 2;if(nums[mid] < nums[right]) right = mid;else if(nums[mid] > nums[right]) left = mid+1;else right--;}return nums[left];}
}

        每日一题,今天是困难题。这道题目考察的二分很有意思。

        读完题目,发现这道题就是让我们去寻找最小值。那最暴力的方法也就是O(n)的方法,直接循环一次数组就可以得到最小值了。

        二分的方法怎么做呢?题目这里是会旋转数组的,也就是说,不知道数组会怎么样被选择,但,不论怎么旋转其实都可以知道有一个断点(当然,前后必须是连起来的,也就是0下标的前面对应的是nums.length-1下标的数)。这里用left,right来记录左右边界。由于一开始是升序的数组,那么一定可以知道right下标对应的数是断点之后最大的数。我们分情况来看。

        1.有旋转,且旋转没有刚好复原

        这种情况下,断点一定在数组中间,至少不会在边界0和 len-1的地方,那么这时候lerft所指向的数一定是大于等于right的,因为原数组是递增的。这时候的中点由于在中间,有3种情况:

        (1)如果nums[mid]>nums[right]说明,mid所在的位置,一定在断点之前。因为nums[left]都大于等于nums[right]了,nums[mid]又大于nums[right],所以这时候说明mid左边都还是递增的。由于大于nums[right],说明mid的左边不可能有比right小的,所以left = mid+1。

        (2)如果nums[mid]<nums[right]说明,mid所在的位置,由于小于nums[right],一定在断点之后。因为nums[right]是断点之后最大的,而nums[left]又大于等于right,所以说明此时mid的右边是都是递增的,还没有到达断点。right = mid。

        (3)如果nums[mid] == nums[right]有可能自mid之后都是nums[right]的值,也就是一条直线,这时候要往后退一个位置。因为即使退一个位置,right的值也不会变,而mid的值却可以往后退1位,就可以再进行判断。如果这时候直接让right=mid,有可能错过断点的位置。

       2.顺序

        顺序的话其实right就是最大的,会一直往左边退,直到退到0的位置。

        3.逆序

        逆序实际上right是最小的,会一直往右边进,直到right的位置。

        这道题目对二分的理解很有帮助。

 

相关文章:

【每日一题】154. 寻找旋转排序数组中的最小值 II

154. 寻找旋转排序数组中的最小值 II - 力扣&#xff08;LeetCode&#xff09; 已知一个长度为 n 的数组&#xff0c;预先按照升序排列&#xff0c;经由 1 到 n 次 旋转 后&#xff0c;得到输入数组。例如&#xff0c;原数组 nums [0,1,4,4,5,6,7] 在变化后可能得到&#xff1…...

Linux中如何获取输入设备(如触摸屏、按键等)的事件信息

Linux中如何获取输入设备&#xff08;如触摸屏、按键等&#xff09;的事件信息 在Linux中&#xff0c;可以使用getevent命令来获取输入设备&#xff08;如触摸屏、按键等&#xff09;的事件信息。如果你想在C程序中获取输入设备事件&#xff0c;可以使用以下步骤&#xff1a; …...

Java学习day05:排序,选择、冒泡、快速、二分、杨辉三角

声明&#xff1a;该专栏本人重新过一遍java知识点时候的笔记汇总&#xff0c;主要是每天的知识点题解&#xff0c;算是让自己巩固复习&#xff0c;也希望能给初学的朋友们一点帮助&#xff0c;大佬们不喜勿喷(抱拳了老铁&#xff01;) Java学习day05&#xff1a;排序&#xff0…...

Mybatis的mapper.xml批量插入、修改sql

今天要有个功能&#xff0c;要进行一批数据的插入和修改&#xff0c;为了不频繁调用数据库&#xff0c;所以想到了批量插入和修改&#xff0c;因为从毕业后&#xff0c;就没写过批量插入和批量修改&#xff0c;所以在这里记录一下&#xff0c;避免后续再遇到忘记怎么写了 批量…...

Centos7部署单机版MongoDB

目录 Centos7部署单机版MongoDBMongoDB介绍数据模型索引分布式高可用性查询语言驱动和社区用途缺点 下载并解压安装包创建相关文件夹和文件编辑mongod.conf文件启动mongodb创建管理员用户终止MongoDB服务配置自启动服务关闭SELinux编辑自启动服务文件mongodb服务命令 Centos7部…...

Docker实战-第一章欢迎来到Docker世界

Docker基础 什么是Docker docker是包括一个命令行程序、后台守护进程和一组远程服务&#xff0c;它简化了安装、运行、发布和删除软件的工作。docker实现的基础是UNIX的容器技术。所以在docker出世之前已经有容器的概念&#xff0c;而且像谷歌一类公司也在探索自己的容器&…...

初识C语言——详细入门一(系统性学习day4)

目录 前言 一、C语言简单介绍、特点、基本构成 简单介绍&#xff1a; 特点&#xff1a; 基本构成&#xff1a; 二、认识C语言程序 标准格式&#xff1a; 简单C程序&#xff1a; 三、基本构成分类详细介绍 &#xff08;1&#xff09;关键字 &#xff08;2&#xf…...

python 学习笔记(6)—— Flask 、MySql

目录 Flask 1、起步 2、渲染项目的首页 3、处理无参数的 GET 请求 4、处理有 query 参数的 GET 请求 6、处理 params 参数的 get 请求 6、处理 application/json 类型请求体的 POST 请求 7、根据参数渲染模板页面 8、上传文件 数据库操作&#xff08;mysql&#xff0…...

Deepin下vsftp服务安装配置虚拟用户

1. 系统环境 Deepin20.9 2. 在线安装 # apt install -y vsftp //安装ftp服务软件 # apt install -y db-util //安装虚拟用户密码库处理软件 3. 离线安装 3.1 下载依赖包 # apt-get download $(apt-cache depends --recurse --no-recommends --no-suggests --n…...

OpenpyxlWriter‘ object has no attribute ‘save‘

问题 将实验结果保存为EXCEL&#xff0c;报错“OpenpyxlWriter‘ object has no attribute ‘save‘” data_df pd.DataFrame(Experiment_result) #关键1&#xff0c;将ndarray格式转换为DataFrame writer pd.ExcelWriter(./results/ args.model_num _args.data_name …...

ES6(三)

文章目录 Promise概念作用回调地狱Promise使用对象的状态Promise.allPromise.race Generator 函数概念基本语法异步流程 Class语法类的写法getter与setter静态属性和静态方法继承模块化 Promise 概念 Promise 是异步编程的一种解决方案&#xff0c;比传统的解决方案回调函数,…...

Android 数据库封装(SQLite)

Android 数据库操作&#xff08;SQLite&#xff09; Android 数据库操作&#xff08;SQLite&#xff09;动态预览使用初始化生成表实体类插入数据批量插入删除数据删除全部修改数据查找&#xff08;列表&#xff09;查找&#xff08;单条&#xff09;条件查找&#xff08;列表&…...

Git从入门到起飞(详细)

Git从入门到起飞 Git从入门到起飞什么是Git&#xff1f;使用git前提(注册git)下载Git在Windows上安装Git在macOS上安装Git在Linux上安装Git 配置Git配置全局用户信息配置文本编辑器 创建第一个Git仓库初始化仓库拉取代码添加文件到仓库提交更改推送 Git基本操作查看提交历史比较…...

R读写parquet文件

什么是parquet文件 Apache Parquet是一个开源的&#xff0c;列存储的数据文件格式。 https://parquet.apache.org/ 在R里面&#xff0c;我们可以通过arrow包来读写它。 我们先安装一下arrow包&#xff0c;并加载它。 install.packages("arrow") library(arrow)读写…...

Java21 LTS版本

一、前言 除了众所周知的 JEP 之外&#xff0c;Java 21 还有更多内容。首先请确认 java 版本&#xff1a; $ java -version openjdk version "21" 2023-09-19 OpenJDK Runtime Environment (build 2135-2513) OpenJDK 64-Bit Server VM (build 2135-2513, mixed mo…...

【性能优化】虚拟懒加载(下拉滚动加载长列表)element-puls+el-table

目录 前言一、卡顿的原因&#xff1f;二、解决1、滚动懒加载2.官方 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 在element-plus中&#xff0c;如果数据超过1k&#xff0c;就会感觉到明显的卡顿&#xff0c;应该是渲染的卡顿吧。反正我在请求回…...

一对多映射处理

8.3.1 、collection /** * 根据部门id查新部门以及部门中的员工信息 * param did * return */ Dept getDeptEmpByDid(Param("did") int did);<resultMap id"deptEmpMap" type"Dept"> <id property"did" column"did&quo…...

关于IDEA没有显示日志输出?IDEA控制台没有显示Tomcat Localhost Log和Catalina Log 怎么办?

问题描述&#xff1a; 原因是;CATALINA_BASE里面没有相关的文件配置。而之前学习IDEA的时候&#xff0c;把这个文件的位置改变了。导致&#xff0c;最后输出IDEA的时候&#xff0c;不会把日志也打印出来。 检查IDEA配置; D:\work_soft\tomcat_user\Tomcat10.0\bin 在此目录下&…...

蛇形填数 rust解法

蛇形填数。 在nn方阵里填入1&#xff0c;2&#xff0c;…&#xff0c;nn&#xff0c;要求填成蛇形。例如&#xff0c;n&#xff1d;4时方阵为&#xff1a; 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 解法如下&#xff1a; use std::io;fn main() {let mut buf String::new();…...

一文探索SD-WAN技术进阶后与MPLS的区别

在网络通信领域&#xff0c;随着云计算和大数据等新兴技术的快速发展&#xff0c;企业对于网络的可靠性、安全性以及带宽的需求越来越高。 SD-WAN&#xff08;软件定义广域网&#xff09;和MPLS&#xff08;多协议标签交换&#xff09;是两种不同的网络连接技术&#xff0c;它们…...

RocketMq(四)消息分类

一、普通消息 1、同步发送消息&#xff1a;指的是Producer发出⼀条消息后&#xff0c;会在收到MQ返回的ACK之后才发下⼀条消息。该方式的消息可靠性最高&#xff0c;但消息发送效率低。 二、顺序消息 三、延时消息...

ip地址怎么改网速快

在当今高度依赖互联网的时代&#xff0c;快速稳定的网络连接对于人们的生活和工作至关重要。然而&#xff0c;有时我们可能会遇到网络速度缓慢的问题。虽然更改IP地址并不能直接影响网络速度&#xff0c;但它可以成为改善网络连接的一种策略之一。虎观代理小二二将探讨如何通过…...

植物大战僵尸各种僵尸攻略(四)

前言 此文章为“植物大战僵尸”专栏中的011刊&#xff08;2023年9月第十刊&#xff09;&#xff0c;欢迎订阅。版权所有。 注意&#xff1a; 1.本博客适用于pvz无名版&#xff1b; 2.pvz指植物大战僵尸&#xff08;Plants VS Zonbies)&#xff1b; 3.本文以耗费低做标准&am…...

main函数中两个参数的作用

一般我们在使用C语言时不太用到main函数自带的参数&#xff0c;因此最常见的main函数就像下面这样。 int main() {...... }上面这种main函数是省略了其形参的&#xff0c;C语言中规定main函数的参数只能有两个&#xff0c;习惯上这两个参数写为argc和argv&#xff0c;其中&…...

华为OD机试 - 连续字母长度 - 字符串(Java 2023 B卷 100分)

目录 专栏导读一、题目描述二、输入描述三、输出描述1、输入2、输出3、说明4、再输入5、输出6、说明 四、解题思路五、Java算法源码六、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08…...

想要精通算法和SQL的成长之路 - 填充书架

想要精通算法和SQL的成长之路 - 填充书架 前言一. 填充书架1.1 优化 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 填充书架 原题链接 题目中有一个值得注意的点就是&#xff1a; 需要按照书本顺序摆放。每一层当中&#xff0c;只要厚度不够了&#xff0c;当前层最高…...

【ROS入门】ROS的核心概念

文章结构 通信机制节点(Node)——执行单元节点管理器(ROS Master)——控制中心话题通信——异步通信机制话题(Topic)消息(Message)——话题数据 服务通信——同步通信机制服务(Service) 话题和服务的区别参数(Parameter)——全局共享字典 文件系统功能包&#xff08;Package&am…...

Python爬虫从端到端抓取网页

网页抓取和 REST API 简介 网页抓取是使用计算机程序以自动方式从网站提取和解析数据的过程。这是创建用于研究和学习的数据集的有用技术。虽然网页抓取通常涉及解析和处理 HTML 文档&#xff0c;但某些平台还提供 REST API 来以机器可读格式&#xff08;如 JSON&#xff09;检…...

这10款类似Stable Diffusion的ai绘图软件,你了解多少?

Stable Diffusion这款ai软件有哪些可以替代的软件&#xff1f;好用的类似Stable Diffusion的ai软件推荐&#xff0c;那么今天就跟着赞奇云工作站小编一起来看看吧。 什么是Stable Diffusion&#xff1f; 称为“Stable Diffusion”的文本到图像模型可以将任何文本转换为逼真、…...

部署ik分词器

部署ik分词器 案例版本&#xff1a;elasticsearch-analysis-ik-8.6.2 ​ ES默认自带的分词器对中文处理不够友好&#xff0c;创建倒排索引时可能达不到我们想要的结果&#xff0c;然而IK分词器能够很好的支持中文分词 ​ 因为是集群部署&#xff0c;所以每台服务器中的ES都需…...