使用二分法解决旋转数组的最小数字的问题

简介: 使用二分法解决旋转数组的最小数字的问题

旋转数组的最小数字


有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样的。请问,给定这样一个旋转数组,求数组中的最小值。

要求:空间复杂度:O(1)O(1) ,时间复杂度:O(logn)O(logn)

示例1:

输入:[3,4,5,1,2]

返回: 1

示例2:

输入:[3,100,200,3]

返回: 3


解题思路


暴力解法可以挨个遍历数组,寻找最小值,但是子题目要求:空间复杂度:O(1)O(1) ,时间复杂度:O(logn)O(logn),这就需要用一些技巧了

首先旋转数组将原本有序的数组分成了两部分有序的数组,因为在原始有序数组中,最小的元素一定是在首位,旋转后无序的点就是最小的数字。旋转后我们可以把数组分为AB两个区域,可以知道A区域所有的值都大于B区域

用两个指针,分别指向最左侧left和最右侧right,再获取一个中间指针mid;以区间[left,right]的最右侧的值为基准,使中间值与它比较;慢慢缩小区域,当left大于等于right时,就找到了最小值

具体步骤如下:

  • 第一步:初始化左右指针,双指针指向旋转后数组的首尾,作为区间端点。
  • 第二步:当左指针小于右指针则进入循环
  • 计算获取中间指针
  • 若是区间中点值小于区间右界值,则最小的数字一定在中点左边。 right = mid
  • 若是区间中点值大于区间右界值,则最小的数字一定在中点右边。left = mid+1
  • 若是区间中点值等于区间右界值,则是不容易分辨最小数字在哪半个区间,应该逐个缩减右界令right--
  • 第三步:当left大于等于right时,就找到了最小值,返回rotateArray[left]
function minNumberInRotateArray(rotateArray){
  let left = 0
  let right = rotateArray.length-1;
  while(left < right){
    let mid = Math.floor( (left + right)/2 );
    if(rotateArray[mid] < rotateArray[right]){
      right = mid;
    }else if(rotateArray[mid] > rotateArray[right]){
      left = mid+1;
    }else{
      right--;
    }
  }
  return rotateArray[left];
}


image.png


目录
相关文章
|
存储 分布式计算 安全
分布式文件系统介绍与minio介绍与使用(附minio java client 使用)(一)
分布式文件系统介绍与minio介绍与使用(附minio java client 使用)
682 0
|
SQL 缓存 Oracle
关系型数据库Oracle性能问题
【7月更文挑战第16天】
196 2
|
SQL 关系型数据库 MySQL
Hive 表注释乱码解决
Hive元数据在MySQL默认使用`latin1`字符集导致注释乱码。可通过修改MySQL配置文件`/etc/my.cnf`,在`[mysqld]`和末尾添加`character-set-server=utf8`等设置,重启MySQL。然后在Hive数据库中调整表字段、分区字段、索引注释的字符集。注意,这仅对新表生效。测试创建带注释的Hive表,问题解决。
333 0
|
监控 数据处理 调度
使用Apache Airflow进行工作流编排:技术详解与实践
【6月更文挑战第5天】Apache Airflow是开源的工作流编排平台,用Python定义复杂数据处理管道,提供直观DAGs、强大调度、丰富插件、易扩展性和实时监控。本文深入介绍Airflow基本概念、特性,阐述安装配置、工作流定义、调度监控的步骤,并通过实践案例展示如何构建数据获取、处理到存储的工作流。Airflow简化了复杂数据任务管理,适应不断发展的数据技术需求。
2367 3
|
分布式计算 DataWorks 大数据
MaxCompute产品使用合集之在MaxCompute中环境变量该怎么设置
MaxCompute作为一款全面的大数据处理平台,广泛应用于各类大数据分析、数据挖掘、BI及机器学习场景。掌握其核心功能、熟练操作流程、遵循最佳实践,可以帮助用户高效、安全地管理和利用海量数据。以下是一个关于MaxCompute产品使用的合集,涵盖了其核心功能、应用场景、操作流程以及最佳实践等内容。
|
存储 算法 Unix
|
机器学习/深度学习 数据采集 算法
GEE机器学习——利用支持向量机SVM进行土地分类和精度评定
GEE机器学习——利用支持向量机SVM进行土地分类和精度评定
648 0
|
C语言
【C 语言经典100例】C 练习实例30 - 回文数
【C 语言经典100例】C 练习实例30 - 回文数
93 0
|
存储 算法 安全
计算机操作系统课后习题答案(2)
23.在生产者消费者问题中,如果缺少了signal(full)或signal(empty),对执行结果有何影响? 答: 如果缺少signal(full),那
888 0
|
Kubernetes Go 数据安全/隐私保护
两个生僻小命令---go mod why和go mod graph
两个生僻小命令---go mod why和go mod graph
945 0