leetcode (力扣) 154. 寻找旋转排序数组中的最小值 I+II (二分法)

news/2024/11/8 23:08:02/

文章目录

  • 题目描述
  • 思路分析
  • 完整代码

题目描述

已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,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) 的算法解决此问题。

示例 2:
输入:nums = [2,2,2,0,1]
输出:0

思路分析

寻找旋转排序数组中的最小值有俩题,一个中等一个困难,区别就在于数组中是否有重复数字。

先说一下中等的这个题。

题目要求:
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
无疑直接二分法。

例子:nums = [4,5,6,7,0,1,2,3]

直接设置头尾指针,left=0 。right = len(nums)-1。
开始二分。

这里的关键点就在于如何划分后续的left和right。

直接看一遍步骤:

  • mid = (left+right)//2 = 3
  • 此时mid指向数组中的7,显然最小值还在右边,所以当nums[mid]>nums[right]时,left = mid+1
  • 同理,小于的时候 right = mid,这里要找的是最小值,所以当大于的时候可以直接+1跳过mid,小于的时候由于并无法确定mid是否为最小值,所以不能+1跳过。

然后二分就结束了。这题就是这么简单。

再说一下这个困难题

困难题目在中等的基础上加了一个条件,就是数组中可能存在相同的元素。

假设有例子 nums=[4.5.6.7.0.1.1]

  • 开始时mid指向7,right指向1.显然数组向右边收缩。
  • left = 4,mid=5,right=6.此时 nums[mid] == nums[right],所以right = right-1.去掉重复值,然后继续循环。

细节:
为什么本题二分法不用 nums[m] 和 nums[i] 作比较?

二分目的是判断 m 在哪个排序数组中,从而缩小区间。而在 nums[m]>nums[i],情况下,无法判断 m 在哪个排序数组中。本质上是由于 j 初始值肯定在右排序数组中; i 初始值无法确定在哪个排序数组中。举例如下:

对于以下两示例,当 i=0,j=4,m=2 时,有 nums[m] > nums[i] ,而结果不同。

  • [1,2,3,4,5]旋转点 x=0 : m 在右排序数组(此示例只有右排序数组)。
  • [3,4,5,1,2]旋转点 x=3 : m 在左排序数组。

完整代码

153题。
class Solution:def findMin(self, nums: List[int]) -> int:left = 0right = len(nums)-1while left<right:mid =  (left+right)//2if nums[mid] > nums[right]:left = mid+1else:right = midreturn nums[left]154题。
class Solution:def findMin(self, nums: List[int]) -> int:left = 0right = len(nums)-1while left<right:mid = (left+right)//2if nums[mid]>nums[right]:left = mid+1elif nums[mid]<nums[right]:right = midelse:right-=1return nums[left]

http://www.ppmy.cn/news/1255043.html

相关文章

《凤凰项目》读书笔记

文章目录 一、书名和作者二、书籍概览2.1 主要论点和结构2.2 目标读者和应用场景 三、核心观点与主题3.1 DevOps的核心原则与文化变革3.2 持续交付与自动化3.3 变更管理与风险控制3.4 关键绩效指标与持续改进 四、亮点与启发4.1 最有影响的观点4.2 对个人专业发展的启示 五、批…

微信小程序实现watch监听数值改变的效果

前言 需要用到Javascript中的Object.defineProperty()方法&#xff0c;实现劫持对象的get/set指令&#xff0c;从而监听到对象的赋值(调用setter)&#xff0c;达到监听数值改变效果 示例 监听变量方法&#xff1a; function watchData(pageData, key, fn) {var oldVal pag…

Docker、Kubernetes、OCI、CRI-O、containerd、runc 之间的关系以及它们是如何一起工作的?

最近网上看到一张图片&#xff0c;能够很清晰地展现出 Docker、Kubernetes、OCI、CRI-O、containerd、runc 之间的关系以及它们是如何在一起工作的&#xff0c;如下&#xff1a; 本文可以作为之前一篇文章&#xff08;《K8s、Docker、CRI、OCI 之间的爱恨情仇》&#xff09;的…

Python快速实现BMI(身体质量指数)计算器(窗口界面形式)

BMI是身体质量指数&#xff08;Body Mass Index&#xff09;的缩写&#xff0c;是一种衡量人体肥胖程度的指标。它是根据人的身高和体重计算得出的&#xff0c;公式为&#xff1a; BMI 体重&#xff08;kg&#xff09;/ 身高^2&#xff08;m&#xff09; 其中&#xff0c;体…

【算法】直接插入排序

目录 1. 说明2. 举个例子3. java代码示例4. java示例截图 1. 说明 1.直接插入排序的方式和打牌一样&#xff0c;刚开始数组为空 2.拿到一个数字后从左到右将它与数组中的每一个数字进行比较&#xff0c;然后插入合适的位置 3.到最后&#xff0c;数组按照既定的顺序排序好 2. 举…

【SpringMVC】Spring Web MVC入门(一)

文章目录 前言什么是Spring Web MVC&#xff1f;什么是MVC什么是Spring MVC&#xff1f; Spring Boot 和 Spring MVC 的区别什么是Spring Boot&#xff1f;关系和区别 Spring MVC 学习注解介绍1. SpringBootApplication2. RestController3. RequestMapping3.1 RequestMapping 使…

javascript的Proxy

1. 什么是Proxy Proxy是ES6中新增的一个特性&#xff0c;它可以拦截对象的操作&#xff0c;提供了一个中间层来控制对目标对象的访问。简单来说&#xff0c;它可以对对象进行代理&#xff0c;从而实现对对象的监控、修改、过滤等操作。 2. 为什么出现Proxy 在JavaScript中&a…

Session 与 JWT 的对决:谁是身份验证的王者? (下)

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…