寻找旋转排序数组中的最小值[中等]

news/2024/4/20 23:41:27/文章来源:https://blog.csdn.net/zhengzhaoyang122/article/details/136547430

在这里插入图片描述

优质博文IT-BLOG-CN

一、题目

已知一个长度为n的数组,预先按照升序排列,经由1n次 旋转 后,得到输入数组。例如,原数组nums = [0,1,2,4,5,6,7]在变化后可能得到:
【1】若旋转4次,则可以得到[4,5,6,7,0,1,2]
【2】若旋转7次,则可以得到[0,1,2,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,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为O(log n)的算法解决此问题。

示例 1:
输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为[1,2,3,4,5],旋转3次得到输入数组。

示例 2:
输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为[0,1,2,4,5,6,7],旋转3次得到输入数组。

示例 3:
输入:nums = [11,13,15,17]
输出:11
解释:原数组为[11,13,15,17],旋转4次得到输入数组。

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums中的所有整数 互不相同
nums原来是一个升序排序的数组,并进行了1n次旋转

二、代码

二分查找

我们考虑数组中的最后一个元素xxx:在最小值右侧的元素(不包括最后一个元素本身),它们的值一定都严格小于xxx;而在最小值左侧的元素,它们的值一定都严格大于xxx。因此,我们可以根据这一条性质,通过二分查找的方法找出最小值。

在二分查找的每一步中,左边界为low,右边界为high,区间的中点为pivot,最小值就在该区间内。我们将中轴元素nums[pivot]与右边界元素nums[high]进行比较,可能会有以下的三种情况:

第一种情况是nums[pivot]<nums[high]。这说明nums[pivot]是最小值右侧的元素,因此我们可以忽略二分查找区间的右半部分。

第二种情况是nums[pivot]>nums[high]。这说明nums[pivot]是最小值左侧的元素,因此我们可以忽略二分查找区间的左半部分。

由于数组不包含重复元素,并且只要当前的区间长度不为1pivot就不会与high重合;而如果当前的区间长度为1,这说明我们已经可以结束二分查找了。因此不会存在nums[pivot]=nums[high]的情况。

当二分查找结束时,我们就得到了最小值所在的位置。

class Solution {public int findMin(int[] nums) {int low = 0;int high = nums.length - 1;while (low < high) {int pivot = low + (high - low) / 2;if (nums[pivot] < nums[high]) {high = pivot;} else {low = pivot + 1;}}return nums[low];}
}

时间复杂度: 时间复杂度为O(log⁡n),其中n是数组nums的长度。在二分查找的过程中,每一步会忽略一半的区间,因此时间复杂度为O(log⁡n)

空间复杂度: O(1)

主要思路

单调递增的序列:

        ****
*

做了旋转:

  *
****

用二分法查找,需要始终将目标值(这里是最小值)套住,并不断收缩左边界或右边界。

左、中、右三个位置的值相比较,有以下几种情况:

    左值 < 中值, 中值 < 右值 :没有旋转,最小值在最左边,可以收缩右边界右中左

左值 > 中值, 中值 < 右值 :有旋转,最小值在左半边,可以收缩右边界

     左       右中

左值 < 中值, 中值 > 右值 :有旋转,最小值在右半边,可以收缩左边界

         中  左 右

左值 > 中值, 中值 > 右值 :单调递减,不可能出现

     左中右

分析前面三种可能的情况,会发现情况12是一类,情况3是另一类。
【1】如果中值 < 右值,则最小值在左半边,可以收缩右边界。
【2】如果中值 > 右值,则最小值在右半边,可以收缩左边界。
【3】通过比较中值与右值,可以确定最小值的位置范围,从而决定边界收缩的方向。

而情况1与情况3都是左值 < 中值,但是最小值位置范围却不同,这说明,如果只比较左值与中值,不能确定最小值的位置范围。所以我们需要通过比较中值与右值来确定最小值的位置范围,进而确定边界收缩的方向。

接着分析解法里的一些问题:首先是while循环里的细节问题。这里的循环不变式是left < right, 并且要保证左闭右开区间里面始终套住最小值。

中间位置的计算:mid = left + (right - left) / 2这里整数除法是向下取整的地板除,mid更靠近left,再结合while循环的条件left < right,可以知道left <= mid,mid < right,即在while循环内,mid始终小于right。因此在while循环内,nums[mid]要么大于要么小于nums[right],不会等于。这样else {right = mid;}这句判断可以改为更精确的else if (nums[mid] < nums[right]) {right = mid;}

再分析一下while循环退出的条件。

如果输入数组只有一个数,左右边界位置重合,left == right,不会进入while循环,直接输出。

如果输入数组多于一个数,循环到最后,会只剩两个数,nums[left] == nums[mid],以及nums[right],这里的位置left == mid == right - 1

如果nums[left] == nums[mid] > nums[right],则左边大、右边小,需要执行left = mid + 1,使得left == right,左右边界位置重合,循环结束,nums[left]与nums[right]都保存了最小值。

如果nums[left] == nums[mid] < nums[right],则左边小、右边大,会执行right = mid,使得left == right,左右边界位置重合,循环结束,nums[left]nums[mid]nums[right]都保存了最小值。

细化了的代码:

class Solution {public int findMin(int[] nums) {int left = 0;int right = nums.length - 1;                /* 左闭右闭区间,如果用右开区间则不方便判断右值 */ while (left < right) {                      /* 循环不变式,如果left == right,则循环结束 */int mid = left + (right - left) / 2;    /* 地板除,mid更靠近left */if (nums[mid] > nums[right]) {          /* 中值 > 右值,最小值在右半边,收缩左边界 */ left = mid + 1;                     /* 因为中值 > 右值,中值肯定不是最小值,左边界可以跨过mid */ } else if (nums[mid] < nums[right]) {   /* 明确中值 < 右值,最小值在左半边,收缩右边界 */ right = mid;                        /* 因为中值 < 右值,中值也可能是最小值,右边界只能取到mid处 */ }}return nums[left];    /* 循环结束,left == right,最小值输出nums[left]或nums[right]均可 */     }
};

再讨论一个问题: 为什么左右不对称?为什么比较midright而不比较midleft?能不能通过比较midleft来解决问题?

左右不对称的原因是: 这是循环前升序排列的数,左边的数小,右边的数大,而且我们要找的是最小值,肯定是偏向左找,所以左右不对称了。

为什么比较midright而不比较midleft
具体原因前面已经分析过了,简单讲就是因为我们找最小值,要偏向左找,目标值右边的情况会比较简单,容易区分,所以比较midright而不比较midleft

那么能不能通过比较midleft来解决问题?
能,转换思路,不直接找最小值,而是先找最大值,最大值偏右,可以通过比较midleft来找到最大值,最大值向右移动一位就是最小值了(需要考虑最大值在最右边的情况,右移一位后对数组长度取余)。

以下是先找最大值的代码,可以与前面找最小值的比较:

class Solution {public int findMin(int[] nums) {int left = 0;int right = nums.length - 1; while (left < right) {int mid = left + (right - left + 1) / 2;   /* 先加一再除,mid更靠近右边的right */if (nums[left] < nums[mid]) {left = mid;                            /* 向右移动左边界 */} else if (nums[left] > nums[mid]) {right = mid - 1;                       /* 向左移动右边界 */}}return nums[(right + 1) % nums.length];    /* 最大值向右移动一位就是最小值了(需要考虑最大值在最右边的情况,右移一位后对数组长度取余) */}
};

使用left < rightwhile循环条件可以很方便推广到数组中有重复元素的情况,只需要在nums[mid] == nums[right]时挪动右边界就行:

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]) {left = mid + 1;} else if (nums[mid] < nums[right]) {right = mid;} else {right--;}}return nums[left];}
};

初始条件是左闭右闭区间,right = nums.size() - 1,那么能否将while循环的条件也选为左闭右闭区间left <= right

可以的,代码如下:

class Solution {public int findMin(int[] nums) {int left = 0;int right = nums.length - 1; while (left <= right) {                         // 循环的条件选为左闭右闭区间left <= rightint mid = left + (right - left) / 2;if (nums[mid] >= nums[right]) {             // 注意是当中值大于等于右值时,left = mid + 1;                         // 将左边界移动到中值的右边} else {                                    // 当中值小于右值时right = mid;                            // 将右边界移动到中值处}}return nums[right];                             // 最小值返回nums[right]}
};

这道题还有其它解法: 始终将nums[mid]与最右边界的数进行比较,相当于在每次裁剪区间之后始终将最右边的数附在新数组的最右边。

class Solution {public int findMin(int[] nums) {int right_boundary = nums[nums.length - 1];int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > right_boundary) {          left = mid + 1;} else {                                right = mid;}}return nums[left];}
};

或者在处理了第一种情况之后,始终将nums[mid]与最左边界的数nums[0]进行比较,即相当于在每次裁剪区间之后始终将最左边的数附在新数组的最左边,再不断处理情况2及情况3

class Solution:def findMin(self, nums: List[int]) -> int:left, right = 0, len(nums) - 1if nums[left] < nums[right]:return nums[left]while left < right:mid = (left + right) >> 1if nums[0] > nums[mid]:right = midelse:left = mid + 1return nums[left]

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

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

相关文章

Flink ExecuteGraph构建源码解析

文章目录 前言ExecutionGraph中的主要抽象概念源码核心代码入口源码核心流程&#xff1a; 前言 在JobGraph构建过程中分析了JobGraph的构建过程&#xff0c;本文分析ExecutionGraph的构建过程。JobManager(JobMaster) 根据 JobGraph 生成 ExecutionGraph。ExecutionGraph是JobG…

C++前置声明的学习

【C】C中前置声明的应用与陷阱_前置生命如何使用-CSDN博客 首先&#xff0c;这样写会报错&#xff1a; #pragma once #include "A.h" class B {A a; public:B(void);~B(void); };#include "B.h" B::B(void) { }B::~B(void) { } #pragma once #include &…

URL?后参数有特殊字符问题

前端对于URL的参数不做处理 不处理、用URLDecoder.decode()处理、用URLEncoder.encode()处理、用URLEncoder.encode()处理后再用URLDecoder.decode()处理 结果 前端对于URL的参数用encodeURIComponent(‘XF-OPPZZD-26*316’)处理 结果 前端不处理有&字符时 结果会把后…

前端网络请求异步处理——Promise使用记录

Promise是ES6中新增的一个处理复杂异步请求的工具&#xff0c;其主要形式为&#xff1a; const baseUrl http://localhost:80 export const $request (param {}) > {console.log(请求参数, param)return new Promise((resolve, reject) > {wx.request({url: baseUrl …

海外服务器被DDOS攻击了该怎么办

在当今全球化的时代&#xff0c;越来越多的企业和组织选择将业务拓展至海外市场。然而&#xff0c;随着业务的扩大和网络的延伸&#xff0c;也面临着来自不同地区的网络威胁和攻击风险。如果您的海外服务器遭受了DDOS攻击&#xff0c;以下是一些应对措施&#xff1a; 一、立即断…

【Redis】Redis的应用场景

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;Redis ⛺️稳中求进&#xff0c;晒太阳 Redis的应用场景&#xff1a; 限流 要求10s内只能访问一次 RequestMapping("xian")public String xianLiu(String sign){String sign1 …

力扣刷题

文章目录 1. 双指针1.1 两数之和1.2 三数之和1.3 盛最多水的容器1.4 接雨水 2. 字串2.1 滑动窗口最大值 3. 动态规划4. 多维动态规划4.1 最长回文字串 1. 双指针 1.1 两数之和 思路&#xff1a;因为是有序数组&#xff0c; 1.2 三数之和 题目要求不能重复 思路&#xff1a;三…

简明固体物理--晶体的形成与晶体结构的描述

简明固体物理-国防科技大学 chapter 1 Formation of Crystal Contents and roadmapQuantum Mechanics and atomic structureElectronsOld quantum theoryMethod of Quantum MechanicsDistributing functions of micro-particles BindingCrystal structure and typical crystal…

YOLOv9(2):YOLOv9网络结构

1. 前言 本文仅以官方提供的yolov9.yaml来进行简要讲解。 讲解之前&#xff0c;还是要做一些简单的铺垫。 Slice层不做任何的操作&#xff0c;纯粹是做一个占位层。这样一来&#xff0c;在parse_model时&#xff0c;ch[n]可表示第n层的输出通道。 Detect和DDetect主要区别还…

Java开发从入门到精通(一):Java的基础语法进阶

Java大数据开发和安全开发 &#xff08;一&#xff09;Java注释符1.1 单行注释 //1.2 多行注释 /* */1.3 文档注释 /** */1.4 各种注释区别1.5 注释的特点1.5 注释的快捷键 &#xff08;二&#xff09;Java的字面量&#xff08;三&#xff09;Java的变量3.1 认识变量3.2 为什么…

例行性工作(at,crontab)

目录 单一执行的例行性工作at 语法 选项 时间格式 at的工作文件存放目录 at工作的日志文件 实例 命令总结&#xff1a; 循环执行的例行性工作crond 语法 选项 crontab工作调度对应的系统服务 crontab工作的日志文件 用户定义计划任务的文件所在目录 动态查看 crontab文件格式 文…

集合拆分Lists.partition的使用

集合拆分Lists.partition的使用 集合拆分Lists.partition的使用 需要的包 import com.google.common.collect.Lists;引入maven依赖 <dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>21.0</…

真Unity-Editor二次开发-ScriptableObject 可自定义UI界面

关于ScriptablObject自定义 作为官方指定的&#xff0c;曾经我也吐槽过ScriptableObject很鸡肋&#xff0c;个人曾经也是强烈反对在项目中使用&#xff0c;但直到我今天看到下面这个代码&#xff0c;菜发现其实只是自己太菜鸡而已 --------------不想多写什么 -------------…

Rust组织管理,箱Crate包Package和模块module定义和区别,use关键字作用

Rust 组织管理 任何一门编程语言如果不能组织代码都是难以深入的&#xff0c;几乎没有一个软件产品是由一个源文件编译而成的。 本教程到目前为止所有的程序都是在一个文件中编写的&#xff0c;主要是为了方便学习 Rust 语言的语法和概念。 对于一个工程来讲&#xff0c;组织…

NineData与OceanBase完成产品兼容认证,共筑企业级数据库新生态

近日&#xff0c;云原生智能数据管理平台 NineData 和北京奥星贝斯科技有限公司的 OceanBase 数据库完成产品兼容互认证。经过严格的联合测试&#xff0c;双方软件完全相互兼容、功能完善、整体运行稳定且性能表现优异。 此次 NineData 与 OceanBase 完成产品兼容认证&#xf…

Manz高压清洗机S11-028GCH-High Quality Cleaner 操作使用说明492页

Manz高压清洗机S11-028GCH-High Quality Cleaner 操作使用说明492页

理解 JSON 和 Form-data 的区别

在讨论现代网络开发与API设计的语境下&#xff0c;理解客户端和服务器间如何有效且可靠地交换数据变得尤为关键。这里&#xff0c;特别值得关注的是两种主流数据格式&#xff1a;JSON与Form-data。尽管它们的终极目标一致&#xff0c;即数据传输的高效性和可靠性&#xff0c;但…

wps没保存关闭了怎么恢复数据?数据恢复这样做

WPS文件已成为我们不可或缺的一部分。从撰写报告、制作表格到展示演讲&#xff0c;WPS系列软件为我们提供了极大的便利。然而正如任何电子设备都可能遇到的问题一样&#xff0c;WPS文件有时也可能出现损坏的情况&#xff0c;这无疑给我们的工作带来了不小的困扰。 那么当WPS文件…

RPC——远程过程调用

一、RPC介绍 1.1 概述 RPC&#xff08;Remote Procedure Call Protocol&#xff09; 远程过程调用协议。RPC是一种通过网络从远程计算机程序上请求服务&#xff0c;不需要了解底层网络技术的协议。RPC主要作用就是不同的服务间方法调用就像本地调用一样便捷。 1.2 RPC框架 …

【项目笔记】java微服务:黑马头条(day02)

文章目录 app端文章查看&#xff0c;静态化freemarker,分布式文件系统minIO1)文章列表加载1.1)需求分析1.2)表结构分析1.3)导入文章数据库1.3.1)导入数据库1.3.2)导入对应的实体类 1.4)实现思路1.5)接口定义1.6)功能实现1.6.1)&#xff1a;导入heima-leadnews-article微服务&am…