当前位置: 首页 > news >正文

【剑指offer】旋转数组的最小数字

在这里插入图片描述

  • 👑专栏内容:剑指offer
  • ⛪个人主页:子夜的星的主页
  • 💕座右铭:前路未远,步履不停

目录

  • 一、题目描述
    • 1、题目
    • 2、示例
      • 示例1
      • 示例2
  • 二、题目分析
    • 1、暴力法
    • 2、二分法
  • 三、代码汇总
    • 1、暴力法
    • 2、二分法


一、题目描述

1、题目

剑指offer:旋转数组的最小数字

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

2、示例

示例1

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

输出:1

示例2

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

输出:3

二、题目分析

1、暴力法

旋转数组的原数组是一个非降序数组,也就是说,原数组中的元素是按照从小到大的顺序排列的。当将一个非降序数组旋转后,我们可以把旋转数组分为两部分,一部分是最大的一段非降序子数组,另一部分是最小的一段非降序子数组。旋转数组的最小元素就在这两部分之间。比如,数组[3, 4, 5,1,2] 它的最大的一段非降序子数组是[3,4,5]最小的一段非降序子数组是[1,2] ,而最小元素就是最小的非降序子数组的第一个数。

所以说,非降序数组在旋转之后有一个特征,就是在遍历的时候,原始数组是非递减的,旋转之后,就有可能出现递减,而引起递减的数字,就是最小值。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int n = numbers.size();		//(1)
        int min = numbers[0];		//(2)
        for(int i = 1;i<n;i++) 		//(3)
        {
            if(numbers[i] < numbers[i-1])	//(4)
            {
                min = numbers[i];
                break;			//(5)
            }
        }
        return min;
    }
};

(1)获取旋转数组的长度

(2)让旋转数组中第一个元素为最小值

(3)从第二个元素开始遍历旋转数组

(4)如果当前元素比前一个元素小,证明引出现了递减,那么当前元素就是旋转数组的最小元素

(5)找到了最小元素,跳出循环

2、二分法

我们要知道一件事,暴力查找的过程,本质是排除的过程,但是暴力遍历一次只能排除一个,效率过低。既然是查找,我们就可以用二分查找法来缩减时间复杂度。

前面分析过,旋转数组的最小值位于非降序子数组和旋转子数组的交界处。所以,我们可以使用二分查找来查找旋转子数组的第一个元素,也就是最小值。旋转数组的最小值一定在数组的旋转点左侧或者就是旋转点。因此,在查找过程中,我们需要缩小查找区间,尽可能保留可能包含最小值的区间使用leftright指针确定查找区间,缩小区间的方式是根据mid的值与right的值的大小关系进行判断。如果numbers[mid]>numbers[right],说明最小值在mid的右侧,将left指针移动到mid+1的位置;如果numbers[mid]<numbers[right],说明最小值在mid的左侧或者就是mid,将right指针移动到mid的位置;如果numbers[mid] == numbers[right],说明可能是一个旋转点,也可能不是,将right指针移动一位。

图片来自:Krahets

class Solution {
public:
    int minArray(vector<int>& numbers) {
       int n = numbers.size();
       int left = 0,right = n-1;
       //二分查找
       while(left<right)
       {
           int mid = (left + right)/2;
           if(numbers[mid]>numbers[right])
                 left = mid + 1;
            else if (numbers[mid]<numbers[right])
                right = mid;
            else   
                right --;
       }
       return numbers[left];
    }
};

三、代码汇总

1、暴力法

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int n = numbers.size();		
        int min = numbers[0];		
        for(int i = 1;i<n;i++) 	
        {
            if(numbers[i] < numbers[i-1])	
            {
                min = numbers[i];
                break;			
            }
        }
        return min;
    }
};

2、二分法

class Solution {
public:
    int minArray(vector<int>& numbers) {
       int n = numbers.size();
       int left = 0,right = n-1;
       //二分查找
       while(left<right)
       {
           int mid = (left + right)/2;
           if(numbers[mid]>numbers[right])
                 left = mid + 1;
            else if (numbers[mid]<numbers[right])
                right = mid;
            else   
                right --;
       }
       return numbers[left];
    }
};

相关文章:

  • 手写一个简单的RPC框架
  • 如何创建和编写项目管理计划?
  • 算法设计与分析 实验五 贪心算法
  • 正式环境关闭swagger
  • 动态内存的开辟
  • 【分布式版本控制系统Git】| IDEA 集成 Git 、IDEA 集成 GitHub
  • C语言指针链表
  • 全网最完整,接口测试总结彻底打通接口自动化大门,看这篇就够了......
  • 【JVM虚拟机面试宝典】JVM的内存结构是怎么样的?在JVM中会发生内存溢出的区域有那些?— day06
  • C++ string类
  • 细数那些惊艳一时的 CSS 属性
  • 【C语言】你真的了解结构体吗
  • 可做题2(矩阵快速幂,乘法逆元,exgcd)
  • Mysql用户权限分配详解
  • 一文7个步骤从0到1教你搭建Selenium 自动化测试环境
  • [nginx文档翻译系列] 控制nginx
  • [译] React v16.8: 含有Hooks的版本
  • 08.Android之View事件问题
  • ES6 ...操作符
  • extract-text-webpack-plugin用法
  • input的行数自动增减
  • JavaWeb(学习笔记二)
  • Laravel5.4 Queues队列学习
  • sessionStorage和localStorage
  • vue从创建到完整的饿了么(18)购物车详细信息的展示与删除
  • 从零开始在ubuntu上搭建node开发环境
  • 记一次删除Git记录中的大文件的过程
  • 名企6年Java程序员的工作总结,写给在迷茫中的你!
  • 实战|智能家居行业移动应用性能分析
  • 小程序、APP Store 需要的 SSL 证书是个什么东西?
  • 一起来学SpringBoot | 第十篇:使用Spring Cache集成Redis
  • 正则表达式小结
  • hi-nginx-1.3.4编译安装
  • Unity3D - 异步加载游戏场景与异步加载游戏资源进度条 ...
  • ​DB-Engines 12月数据库排名: PostgreSQL有望获得「2020年度数据库」荣誉?
  • # MySQL server 层和存储引擎层是怎么交互数据的?
  • (1) caustics\
  • (4)通过调用hadoop的java api实现本地文件上传到hadoop文件系统上
  • (Redis使用系列) SpirngBoot中关于Redis的值的各种方式的存储与取出 三
  • (附源码)计算机毕业设计ssm基于B_S的汽车售后服务管理系统
  • (四)鸿鹄云架构一服务注册中心
  • (转)es进行聚合操作时提示Fielddata is disabled on text fields by default
  • .Net调用Java编写的WebServices返回值为Null的解决方法(SoapUI工具测试有返回值)
  • .net反编译的九款神器
  • ::什么意思
  • ?
  • @取消转义
  • [acwing周赛复盘] 第 69 场周赛20220917
  • [Android学习笔记]ScrollView的使用
  • [CC-FNCS]Chef and Churu
  • [ERROR] Plugin 'InnoDB' init function returned error
  • [ExtJS5学习笔记]第三十节 sencha extjs 5表格gridpanel分组汇总
  • [hihocoder1395] 最大权闭合子图
  • [I2C]I2C通信协议详解(二) --- I2C时序及规格指引
  • [IE编程] IE中对网页进行截图的编程接口