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

LeetCode_二分搜索_困难_154.寻找旋转排序数组中的最小值 II

目录

  • 1.题目
  • 2.思路
  • 3.代码实现(Java)

1.题目

已知一个长度为 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 次旋转

进阶:这道题与 寻找旋转排序数组中的最小值 类似,但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗?会如何影响,为什么?

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii

2.思路

(1)二分搜索
本题与153.寻找旋转排序数组中的最小值这题类似,只不过本题中的 nums 数组可能包含重复元素。

相关题目:
LeetCode_二分搜索_中等_33.搜索旋转排序数组
LeetCode_二分搜索_中等_81.搜索旋转排序数组 II
LeetCode_二分搜索_中等_153.寻找旋转排序数组中的最小值

3.代码实现(Java)

//思路1————二分搜索
class Solution {public int findMin(int[] nums) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[right]) {//如果 nums[mid] > nums[right],说明最小值在 mid 右侧left = mid + 1;} else if (nums[mid] < nums[right]) {//如果 nums[mid] < nums[right],说明最小值在 mid 左侧或者就是 mid 本身right = mid;} else {//如果 nums[mid] == nums[right],我们无法判断最小值在 mid 的左侧还是右侧,因此将右边界缩小一位right--;}}return nums[left];}
}

相关文章:

LeetCode_二分搜索_困难_154.寻找旋转排序数组中的最小值 II

目录1.题目2.思路3.代码实现&#xff08;Java&#xff09;1.题目 已知一个长度为 n 的数组&#xff0c;预先按照升序排列&#xff0c;经由 1 到 n 次 旋转 后&#xff0c;得到输入数组。例如&#xff0c;原数组 nums [0,1,4,4,5,6,7] 在变化后可能得到&#xff1a; 若旋转 4…...

面向对象设计模式:创建型模式之建造者模式

一、引入 Build&#xff1a;建造和构建具有建筑结构的大型物体 建楼&#xff1a;打牢地基、搭建框架、然后自下而上一层层盖起来。构建物体&#xff1a;通常需要先建造组成这个物体的各个部分&#xff0c;然后分阶段把它们组装起来 二、建造者模式 2.1 Intent 意图 Separate…...

集成学习boosting、bagging、stacking

目录 一、介绍 二、三种架构学习 &#xff08;1&#xff09;boosting &#xff08;2&#xff09;bagging &#xff08;3&#xff09;stacking 一、介绍&#xff1a; 对于单个模型来说很难拟合复杂的数&#xff0c;模型的抗干扰能力较低&#xff0c;所以我们希望可以集成多…...

数据模型(上):模型分类和模型组成

1.模型分类 ​ 数据模型是一种由符号、文本组成的集合,用以准确表达信息景观,达到有效交流、沟通的目的。数据建模者要求能与来自不同部门,具有不同技术背景,不同业务经验,不同技术水平的人员交流、沟通。数据建模者要了解每个人员的观点,并通过反馈证明理解无误,最终作…...

郑州轻工业大学2022-2023(2) 数据结构题目集 - ZZULI

6-1 线性表元素的区间删除 6-1 线性表元素的区间删除 分数 20 全屏浏览题目 切换布局 作者 DS课程组 单位 浙江大学 给定一个顺序存储的线性表&#xff0c;请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储&#xff0c;并且相对位置不能改变…...

【Python语言基础】——Python MySQL Drop Table

Python语言基础——Python MySQL Drop Table 文章目录Python语言基础——Python MySQL Drop Table一、Python MySQL Drop Table一、Python MySQL Drop Table 删除表 您可以使用 “DROP TABLE” 语句来删除已有的表&#xff1a; 实例 删除 “customers” 表&#xff1a; import…...

2023美团面试真题

面试前需要准备&#xff1a; 1. Java 八股文&#xff1a;了解常考的题型和回答思路&#xff1b; 2. 算法&#xff1a;刷 100-200 道题&#xff0c;记住刷题最重要的是要理解其思想&#xff0c;不要死记硬背&#xff0c;碰上原题很难&#xff0c;但 大多数的解题思路是相通的…...

【微信小程序开发全流程】篇章0:基于JavaScript开发的校园综合类微信小程序的概览

基于JavaScript开发的校园综合类微信小程序的概览 本文仅供学习&#xff0c;未经同意请勿转载 一些说明&#xff1a;上述项目来源于笔者我本科大三阶段2019年电子设计课程项目&#xff0c;在这个项目中&#xff0c;我主要是负责的部分有前端&#xff0c;前后端的对接&#xf…...

如何分析sql性能

1、前言 提到sql性能分析&#xff0c;可能都会想到explain&#xff0c;它在mysql里被称为执行计划&#xff0c;也就是说可以通过该命令看出mysql在通过优化器分析之后如何执行sql。mysql的内置优化器十分强大&#xff0c;它能帮我们把sql再次优化&#xff0c;以最低的成本去执…...

市场营销书籍推荐:《经理人参阅:市场营销》

要学好市场营销有什么好方法&#xff1f;答案是看书&#xff01;比起碎片化地去阅读一些文章或看一些相关视频&#xff0c;读书来得更实在些。倘若能静下心来好好读上一本系统性的市场营销书籍&#xff0c;学好营销管理将不会再是一件难事。然而&#xff0c;问题的关键是&#…...

WPF 控件专题 MediaElement控件详解

1、MediaElement 介绍 MediaElement&#xff1a;表示包含音频和/或视频的控件。 MediaOpened在引发事件之前&#xff0c;ActualWidth控件将ActualHeight报告为零&#xff0c;因为媒体内容用于确定控件的最终大小和位置。 对于仅音频内容&#xff0c;这些属性始终为零。 对于固…...

基于SpringBoot+SpringCloud+Vue前后端分离项目实战 --开篇

本文目录前言做项目的三大好处强强联手(天狗组合)专栏作者简介专栏的优势后端规划1. SpringBoot 和 SpringCloud 的选择2. Mybatis 和 MybatisPlus 和 JPA 的选择3. MySQL 和 Mongodb 的选择4. Redis 和 RocketMQ5. 后端规划小总结后端大纲提前掌握的知识点一期SpringBoot二期S…...

循环队列的实现

我们知道队列的实现可以用单链表和数组&#xff0c;但是循环链表也可以使用这两种方式。首先我们来看看单链表&#xff1a;首先使用单链表&#xff0c;我们需要考虑循环队列的一些特点。单链表实现循环队列我们要考虑几个核心问题&#xff1a;首先我们要区别 解决 空 和 满 的问…...

MTK平台开发入门到精通(休眠唤醒篇)休眠唤醒LPM框架

文章目录 一、lpm驱动源码分析二、设备属性调试文件沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇文章将介绍 lpm 驱动源码分析。 mtk 平台下,其默认的 lpm 机制的源码位置:drivers/misc/mediatek/lpm/ 一、lpm驱动源码分析 目录:drivers/misc/mediatek/lpm/…...

ThreadLocal详解

一、ThreadLocal简介 1、简介 ThreadLocal叫做线程变量&#xff0c;它是一个线程的本地变量&#xff0c;意味着这个变量是线程独有的&#xff0c;是不能与其他线程共享的。这样就可以避免资源竞争带来的多线程的问题。 即 ThreadLocal类用来提供线程内部的局部变量&#xff0…...

利用Cookie劫持+HTML注入进行钓鱼攻击

目录 HTML注入和cookie劫持&#xff1a; 发现漏洞 实际利用 来源 HTML注入和cookie劫持&#xff1a; HTML注入漏洞一般是由于在用户能够控制的输入点上&#xff0c;由于缺乏安全过滤&#xff0c;导致攻击者能将任意HTML代码注入网页。此类漏洞可能会引起许多后续攻击&#…...

【接口汇总】常用免费的API

短信API 短信验证码&#xff1a;可用于登录、注册、找回密码、支付认证等等应用场景。支持三大运营商&#xff0c;3秒可达&#xff0c;99.99&#xff05;到达率&#xff0c;支持大容量高并发。 通知短信&#xff1a;当您需要快速通知用户时&#xff0c;通知短信是最快捷有效的…...

数字信号处理知识点

数字信号处理知识点1 频谱图中&#xff0c;横坐标取值范围的含义2 MATLAB常用函数2.1 波形产生2.2 滤波器分析2.3 滤波器实现2.4 线性系统变换2.5 滤波器设计2.5.1 FIR滤波器2.5.2 IIR滤波器2.6 Transforms(变换)2.7 统计信号处理和谱分析2.8 Windows(窗函数)2.9 Parametric Mo…...

计算机网络第八版——第三章课后题答案(超详细)

第三章 该答案为博主在网络上整理&#xff0c;排版不易&#xff0c;希望大家多多点赞支持。后续将会持续更新&#xff08;可以给博主点个关注~ 第一章 答案 第二章 答案 【3-01】数据链路&#xff08;即逻辑链路&#xff09;与链路&#xff08;即物理链路&#xff09;有何区…...

九龙证券|磷酸亚铁锂是什么?磷酸亚铁锂的特点和性能介绍

磷酸亚铁锂是一种新式锂离子电池电极资料&#xff0c;化学式&#xff1a;LiFePO4&#xff0c;磷酸亚铁锂为近来新开发的锂离子电池电极资料&#xff0c;首要用于动力锂离子电池&#xff0c;作为正极活性物质运用&#xff0c;人们习气也称其为磷酸铁锂。 磷酸亚铁锂的特色和功能…...

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

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...