【leetcode热题】寻找旋转排序数组中的最小值 II

news/2024/5/26 15:16:34/文章来源:https://blog.csdn.net/kiugvui/article/details/136586301
  • 难度: 困难
  • 通过率: 38.7%
  • 题目链接:. - 力扣(LeetCode)

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1:

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

示例 2:

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

说明:

  • 这道题是 寻找旋转排序数组中的最小值 的延伸题目。
  • 允许重复会影响算法的时间复杂度吗?会如何影响,为什么?

解法:

首先举两个例子,下图中左边两幅是非递减数组绘制的图像,右边是旋转后绘制的图像。可以看出,旋转后右侧一定是小于等于左侧的。原数组中最小的值,其实就是右半边的左端点。

既然是排序后的数组,虽然经过了旋转,但是直觉还是告诉我要使用二分查找。二分查找涉及到三个量 lohi,mid。我们的目标是找到右边部分的左端点。

如果 mid 落在左半边,那么 lo=mid+1,否则设置 hi=mid。这样不断缩小范围,最终就能找到这个最低点。

那么如何确定 mid 落在那边呢,由于左半边一定大于等于右半边,因此可以使用 nums[mid] 和左半段左端点比较,如果落在左半段,那么 nums[mid] >= nums[0]。但是落在右半段,也有可能 nums[mid] == nums[0] 啊,因为右侧的右端点可能和左侧左端点的值相同。(上图中第二种情况)

因此我们需要保证左半部分一定大于右半部分,为此,我们只需要做如下操作:

while(nums[lo] == nums[hi]){lo ++;
}

处理完成后,我们在 [lo,hi] 上寻找最小值。若 nums[mid] >= nums[lo] 那么 mid 落在左半部分,否则落在右侧。

经过一些朋友的提醒下,我发现还存在其他一些特殊情况:

特殊情况一:如果数组中所有元素的值都相同,那么 lo 就会一直增加,最终越界。

特殊情况二:如果左右两边相等的元素数量相,那么循环完毕后 lo 就是右半边的左端点。前面提到的二分查找策略此时就失效了。

class Solution {
public:int minNumberInRotateArray(vector<int> nums) {int lo = 0, hi = nums.size();while(lo < hi && nums[lo] == nums.back()){lo ++;}// 特殊情况一,所有元素都相等if(lo == hi){return nums[0];}// 特殊情况二if(nums[lo] < nums.back()){return nums[lo];}int left_min = nums[lo];while(lo < hi){int mid = lo + (hi - lo) / 2;if(nums[mid] >= left_min){lo = mid + 1;}else{hi = mid;}}return nums[lo];}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1005780.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

xss.pwnfunction.com靶机 Warmups

通关要求弹出警告框alert(1337) 没有用户交互 不能使用外链接 在chrome中测试 Ma Spaghet! 通过分析代码我们可以看到它直接用innerHTML将接收的内容赋值 但是我们不能使用<script>标签因为&#xff1a;HTML 5 中指定不执行由 innerHTML 插入的 <script> 标签。 所…

★【二叉搜索树】【修剪二叉搜素树】Leetcode 669. 修剪二叉搜索树

★【二叉搜索树】【修剪二叉搜素树】Leetcode 669. 修剪二叉搜索树 解法1 递归 反复做吧 ---------------&#x1f388;&#x1f388;669. 修剪二叉搜索树 题目链接&#x1f388;&#x1f388;------------------- 解法1 递归 反复做吧 /*** Definition for a binary tree no…

Python逆向:pyc字节码转py文件

一、 工具准备 反编译工具&#xff1a;pycdc.exe 十六进制编辑器&#xff1a;010editor 二、字节码文件转换 在CTF中&#xff0c;有时候会得到一串十六进制文件&#xff0c;通过010editor使用查看后&#xff0c;怀疑可能是python的字节码文件。 三、逆向反编译 将010editor得到…

Pytest测试中的临时目录与文件管理!

在Pytest测试框架中&#xff0c;使用临时目录与文件是一种有效的测试管理方式&#xff0c;它能够确保测试的独立性和可重复性。在本文中&#xff0c;我们将深入探讨如何在Pytest中利用临时目录与文件进行测试&#xff0c;并通过案例演示实际应用。 为什么需要临时目录与文件&a…

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:Stepper)

步骤导航器组件&#xff0c;适用于引导用户按照步骤完成任务的导航场景。 说明&#xff1a; 该组件从API Version 8开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 仅能包含子组件StepperItem。 接口 Stepper(value?: { index?…

前端请求到 SpringMVC 的处理流程

1. 发起请求 客户端通过 HTTP 协议向服务器发起请求。 2. 前端控制器&#xff08;DispatcherServlet&#xff09; 这个请求会先到前端控制器 DispatcherServlet&#xff0c;它是整个流程的入口点&#xff0c;负责接收请求并将其分发给相应的处理器。 3. 处理器映射&#xf…

第十四届蓝桥杯蜗牛

蜗牛 线性dp 目录 蜗牛 线性dp 先求到达竹竿底部的状态转移方程 求蜗牛到达第i根竹竿的传送门入口的最短时间​编辑 题目链接&#xff1a;蓝桥杯2023年第十四届省赛真题-蜗牛 - C语言网 关键在于建立数组将竹竿上的每个状态量表示出来&#xff0c;并分析出状态转移方程 in…

三、HarmonyOS 应用开发入门之运行Hello World

目录 1、课程对象 1.1、有移动端开发经验 1.2、无移动端开发经验 1.3、对 HarmonyOS 感兴趣 2、DevEco Studio 的使用 2.1、DevEco Studio 的关键特性 智能代码编辑 低代码开发 多段双向实时预览 多端模拟仿真 2.2、安装配置 DevEco Studio 2.2.1、官网开发工具下载地…

光网络:SONET、SDH、DWDM的区别

SONET&#xff08;Synchronous Optical Network&#xff09;、SDH&#xff08;Synchronous Digital Hierarchy&#xff09;和DWDM&#xff08;Dense Wavelength Division Multiplexing&#xff09;都是在光纤通信领域中使用的关键技术。它们在提供高容量、高效率、可靠性等方面…

IO复用之select

目录 一.select方法介绍 2.1 select 系统调用的原型 2.2 集合的数据结构 2.2.1 fd_set 结构如下: 2.2.2 关于集合fd_set的解析 2.3 select第一个参数 2.4 select方法之超时时间timeout 2.5 select方法的用法简述及返回值 2.6 如何检测集合中有哪些描述符有事件就绪 三…

基于Yolo5模型的动态口罩佩戴识别安卓Android程序设计

禁止完全抄袭&#xff0c;引用注明出处。 下载地址 前排提醒&#xff1a;文件还没过CSDN审核&#xff0c;GitHub也没上传完毕&#xff0c;目前只有模型的.pt文件可以下载。我会尽快更新。 所使用.ptl文件 基于Yolo5的动态口罩佩戴识别模型的pt文件资源-CSDN文库 项目完整文…

(C语言)strcpy与strcpy详解,与模拟实现

目录 1. strcpy strcpy模拟实现&#xff1a; 实现方法1&#xff1a; 实现方法2&#xff1a; 2. strcat strcat模拟实现&#xff1a; 1. strcpy 作用&#xff1a;完成字符串的复制。 头文件&#xff1a;<string.h> destination是字符串要复制到的地点&#xff0c;s…

qtablewidget 列宽自适应 而不是均分

102&#xff0c;103行就可以实现列宽自适应&#xff0c;但是需要注意&#xff0c;列宽必须先设置也就是99行必须在前。 有个简化写法 明天穿上来

.NET MAUI 社区工具包 2023 年亮点

作者&#xff1a;Kym Phillpotts 排版&#xff1a;Alan Wang 2023 年已经过去了&#xff0c;让我们花点时间回顾一下 .NET MAUI Community Toolkit 项目的历程以及展望接下来的发展。作为 .NET MAUI 的配套产品&#xff0c;该开源库为开发人员提供了一组丰富多样的控件、转换器…

用KNN算法进行鸢尾花分类

K-近邻算法&#xff08;K Nearest Neighbor) KNN算法的核心思想&#xff1a;你的“邻居”来推测你的类别 K的取值&#xff1a; K值取得过小&#xff0c;容易受到异常点的影响 K值取得过大&#xff0c;受样本不均衡的影响 KNN的API sklearn.neighbors.KNeighborsClassifier(n_…

vue 浏览器刷新报404,系统正常访问没问题

这个情况是因为vue的路由出问题了。 采用hash模式即可。 详细请了解&#xff1a; vue router 的两种路由模式hash与history的区别_vue hisotry-CSDN博客 vue默认是是hash

【WEEK2】 【DAY1】第一个MVC程序之使用注解【中文版】

2024.3.4 Monday 接上文 【WEEK1】 【DAY5】第一个MVC程序之配置文件【中文版】 目录 3.2.使用注解&#xff08;在实际使用中用不到3.1&#xff09;3.2.1.新建一个module&#xff0c;名为springmvc-03-hello-annotation&#xff0c;添加web支持3.2.2.由于Maven可能存在资源过…

最新APP开发趋势,探索2024年的创新与挑战

2024年&#xff0c;移动应用市场仍然是创新与变革的焦点。随着技术的不断发展和用户需求的不断变化&#xff0c;APP开发行业也在不断演进。本文将深入探讨2024年最新的APP开发趋势&#xff0c;以及所带来的创新与挑战&#xff0c;并介绍虎克技术公司提出的解决方案。 1. 强调用…

32单片机基础:输入捕获测频率

接线图如下图所示&#xff1a; 我们复制之前写过的代码6-3 PWM驱动LED呼吸灯 在PWM模块中&#xff0c;执行的逻辑是&#xff0c;初始化TIM2的通道1&#xff0c;产生一个PWM波形&#xff0c;输出引脚是PA0&#xff0c;通过SetCompare1的函数&#xff0c;可以调节CCR1寄存器的值…

spring中事务失效的场景有哪些?

异常捕获处理 在方法中已经将异常捕获处理掉并没有抛出。 事务只有捕捉到了抛出的异常才可以进行处理&#xff0c;如果有异常业务中直接捕获处理掉没有抛出&#xff0c;事务是无法感知到的。 解决&#xff1a;在catch块throw抛出异常。 抛出检查异常 spring默认只会回滚非检…