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

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...