(java)旋转数组的最小数字:输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。

标签: 数据结构算法题  算法  数据结构  java  leetcode  剑指offer


题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

思路

这题是用二分法,二分法的变种形式,没有具体的值用来比较。那么用中间值和高低位进行比较,看处于递增还是递减序列,进行操作缩小范围。

  • 处于递增:low上移

  • 处于递减:high下移(如果是high-1,则可能会错过最小值,因为找的就是最小值)

  • 其余情况:low++缩小范围

在这里插入图片描述
在这里插入图片描述

举个例子来说:
最初的时候,low在0号位置,mid在3号位置,high在6号位置

因为array[mid]>array[low]即7大于4,所以low~mid这一区间是递增的,所以我们移动low,使得low=mid+1,并且注意,此时mid也随之移动到low和high的中间
在这里插入图片描述
此时low、mid、high的情况如下:
在这里插入图片描述

因为array[mid]<array[high],所以我们移动high,使得high = mid,此时low、mid、high的情况如下:
在这里插入图片描述

再接下来,又因为array[mid]<array[high],所以我们移动high,使得high = mid,此时low、mid、high的情况如下:在这里插入图片描述
【发现自己举的例子不太好,没有把所有情况都包括在内,不过应该还是能明白的】

代码

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array == null || array.length<=0){
            return 0;
        }
        int low = 0;
        int high = array.length-1;
        int mid = 0;
        while(low<high){
            if (array[low]<array[high]){
                return array[low];
            }
            mid = (low+(high-low))/2;
            if (array[mid]>array[low]){
                low = mid + 1;
            }
            else if(array[mid]<array[high]){
                high = mid;
            }
            else {
                low++;
            }
        }
        return array[high];
    }
}
版权声明:本文为fjswcjswzy原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/fjswcjswzy/article/details/107956231

智能推荐

26_Python基础_继承

面向对象三大特性: 封装 根据 职责 将 属性 和 方法 封装 到一个抽象的 类 中 继承 实现代码的重用, 相同的代码不需要重复的编写 多态 不同的对象调用相同的方法,  产生不同的执行结果,  增加代码的灵活度 1.  单继承 1.1 概念 继承的概念:&...

循环

与任何程序设计语言一样Java利用条件语句与循环结构确定流程控制,一下总结一下Java中的循环语句: while do while for switch 对于golang来说: switch非常灵活。从第一个expr为true的case开始执行,如果case带有fallthrough,程序会继续执行下一条case,不会再判断下一条case的expr,如果之后的case都有fallthrough,d...

1638 统计只差一个字符的子串数目(动态规划)

1. 问题描述: 给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换一个不同字符以后,是 t 串的子串。换言之,请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。比方说, "computer" 和 "computation"...

websocket基本原理

HTTP中一个request只能有一个response。而且这个response也是被动的,不能主动发起 因此过去的服务端推送信息是通过客户端不停的轮询实现的 websocket是双向通信协议,提供了服务端主动推送信息的能力 需要客户端(浏览器)和服务端同时支持 如果经过代理的话,还需要代理支持,否则有些代理在长时间无通信时会自动切断连接 因此WS为了保证连接不被断掉,会发心跳 WebSocket...

mybatis+ehcache二级缓存

导入jar包 mapper.xml文件开启二级缓存 pojo类实现序列化接口 配置ehcache.xml 测试...

猜你喜欢

python+opencv实现图像拼接

任务 拍摄两张图片去除相同部分,拼接在一起 原图 结果 步骤 读取两张图片 使用sift检测关键点及描述因子 匹配关键点 处理并保存关键点 得到变换矩阵 图像变换并拼接 代码实现 扩展 这里对右边图像进行变换,右边变得模糊,可以修改代码对左边图像变换 这里只有两张图片拼接,可以封装实现多张图片拼接 可以修改代码实现上下图片的拼接...

python_sklearn机器学习算法系列之AdaBoost------人脸识别(PCA,决策树)

          注:在读本文之前建议读一下之前的一片文章python_sklearn机器学习算法系列之PCA(主成分分析)------人脸识别(k-NearestNeighbor,KNN)         本文主要目的是通过一个简单的小...

memmove函数与memcpy函数的模拟实现

memmove函数和memcpy函数都是在内存复制任意类型的,但是它俩也有区别。当源区域和目标区域有重复的,memmove函数会复制缓冲区重叠的部分,而memcpy相反,会报出未知错误。 下面给出两个函数的实现 首先,memmove函数。 实现的基本原理如下图。 具体代码如下: memcpy函数的实现很简单,就直接给出源代码了...

SpringFramework核心 - IOC容器的实现 - 总结

1. 概述 把Spring技术内幕第一章和第二章过了一遍,也做了一些笔记, 对IOC容器的实现有了一定皮毛理解,现在跟着源码再过一遍总结一下IOC容器的初始化,Bean的初始化的过程,做一下总结 ① IOC容器和简单工厂模式 在开始之前,先想想我们平时是怎么使用IOC容器为我们管理Bean的,假设我们要把下面的User类交给IOC容器管理 我们不想关心如何创建一个User对象实例的,仅仅在需要他的...