当前位置: 首页 > 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;人们习气也称其为磷酸铁锂。 磷酸亚铁锂的特色和功能…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...