求解旋转数组的最小数字

更新时间：2020年4月25日 17:31 点击：1411

求解旋转数组的最小数字

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小数组。例如数组{3,4,5,1,2}是数组{1,2,3,4,5}的旋转数组，该数组的最小值为1。

思路解析：

O(N)的算法

这种算法的思想就是遍历这个数组，由于这个数组是两部分有序的数组，因此遍历这个数组时当后一个数字小于前一个数字时，则后一个（即较小）一定为整个数组中最小的数字。

这种算法的思想很简单，但就是时间复杂度较大，因此不是很好的算法。

int minNumberInRotateArray(vector<int> rotateArray)
{
  if (rotateArray.empty())
    return -1;

  unsigned int i=0;
  for (; i<rotateArray.size()-1; i++)
  {
    if (rotateArray[i] > rotateArray[i+1])
      break;
  }
  return rotateArray[i+1];
}

O(logN)的算法

这种算法思想类似于二分查找，首先每次找到数组中中间的数字mid，如果mid大于最左端left，说明最小数在mid的右侧区间，则改变left，置left为mid；如果mid小于数组右侧right，说明最小数在mid的左侧区间，则改变right为mid….当left的数字小于等于right的数字时，说明已经找到最小数，这个也是循环结束的条件

int minNumberInRotateArray(vector<int> rotateArray)
{
  if (rotateArray.empty())
    return -1;
  unsigned int left=0;
  unsigned int right=rotateArray.size()-1;
  unsigned int mid=left;
  while (rotateArray[left] >= rotateArray[right])
  {
    if (right-left == 1)
    {
      mid = right;
      break;
    }
    mid = left+((right-left)>>1);

    if (rotateArray[mid]==rotateArray[left] && rotateArray[right]==rotateArray[mid])
      return rotateArray[mid];

    if (rotateArray[mid] >= rotateArray[left])
      left = mid;
    else if (rotateArray[mid] <= rotateArray[right])
      right = mid;
  }
  return rotateArray[mid];
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

[!--infotagslink--]

上一篇: c++插入排序详解

下一篇: c++选择排序详解

php中eval()函数操作数组的方法
在php中eval是一个函数并且不能直接禁用了，但eval函数又相当的危险了经常会出现一些问题了，今天我们就一起来看看eval函数对数组的操作例子， <?php $data="array...2016-11-25
Python 图片转数组,二进制互转操作
这篇文章主要介绍了Python 图片转数组,二进制互转操作，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
php数组操作键名比较差集交集赋值
本文章提供在量的数据中级操作实例有如对键名比较计算数组的差集计算差集给指定数组中插入一个元素反转数组交集赋值新的数组实例。 //定义回调函数 funct...2016-11-25
C#二维数组基本用法实例
这篇文章主要介绍了C#二维数组基本用法,以实例形式分析了C#中二维数组的定义、初始化、遍历及打印等用法,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
C#数组的常用操作方法小结
Array数组在C#中同样是最基本的数据结构,下面为大家C#数组的常用操作方法小结,皆为细小的代码段,欢迎收看收藏...2020-06-25
php curl模拟post请求和提交多维数组的示例代码
下面一段代码给大家介绍php curl模拟post请求的示例代码，具体代码如下： <?php$uri = "http://www.cnblogs.com/test.php";//这里换成自己的服务器的地址// 参数数组$data = array ( 'name' => 'tanteng'// 'passwor...2015-11-24
C# 拷贝数组的几种方法(总结)
下面小编就为大家带来一篇C# 拷贝数组的几种方法(总结)。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
PHP 二维数组根据某个字段排序的具体实现
本文记录的要实现的功能类似于 MySQL 中的 ORDER BY，上个项目中有遇到这样的一个需求。要求：从两个不同的表中获取各自的4条数据，然后整合(array_merge)成一个数组，再根据数据的创建时间降序排序取前4条。遇到这个...2014-06-07
C#实现字符串转换成字节数组的简单实现方法
这篇文章主要介绍了C#实现字符串转换成字节数组的简单实现方法,仅一行代码即可搞定,非常简单实用,需要的朋友可以参考下...2020-06-25
c#将字节数组转成易读的字符串的实现
这篇文章主要介绍了c#将字节数组转成易读的字符串的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
C#读取文件所有行到数组的方法
这篇文章主要介绍了C#读取文件所有行到数组的方法,涉及C#针对文件及数组的相关操作技巧,需要的朋友可以参考下...2020-06-25
将二维数组转为一维数组的2种方法
如何将下面的二维数组转为一维数组。复制代码代码如下:$msg = array(　　array(　　　　'id'=>'45',　　　　'name'=>'jack'　　),　　array(　　　　'id'=>'34',　　　　'name'=>'mary'　　),　　array(　　　　'id...2014-05-31
C#中图片旋转和翻转(RotateFlipType)用法分析
这篇文章主要介绍了C#中图片旋转和翻转(RotateFlipType)用法,实例分析了C#图片旋转及翻转Image.RotateFlip方法属性的常用设置技巧,需要的朋友可以参考下...2020-06-25
php中数组写入文件方法
在php中为我们提供了一个函数var_export 他可以直接将php代码入到一个文件中哦。代码如下复制代码 var_export($times,true);后面不加tru...2016-11-25
PHP 如何获取二维数组中某个key的集合
本文为代码分享，也是在工作中看到一些“大牛”的代码，做做分享。具体是这样的，如下一个二维数组，是从库中读取出来的。代码清单：复制代码代码如下: $user = array( 0 => array( 'id' => 1, 'name' => '张三', 'ema...2014-06-07
js有序数组的连接问题
1.前言昨天碰到一道关于如何解决有序数组的连接问题，这是一个很常见的问题。但是这里要考虑到代码的效率问题，因为要连接的数组都是有序的，这是一个非常重要的前提条件。2.简单但效率不高的算法我首先想到的是使用...2013-10-04
python 实现将Numpy数组保存为图像
今天小编就为大家分享一篇python 实现将Numpy数组保存为图像，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
C#中数组、ArrayList、List、Dictionary的用法与区别浅析(存取数据)
在工作中经常遇到C#数组、ArrayList、List、Dictionary存取数据，但是该选择哪种类型进行存储数据呢？很迷茫，今天小编抽空给大家整理下这方面的内容，需要的朋友参考下吧...2020-06-25
C#中List和数组之间转换的方法
这篇文章主要介绍了C#中List和数组之间转换的方法,涉及比较简单的转换技巧,需要的朋友可以参考下...2020-06-25
javascript中去除数组重复元素的实现方法【实例】
下面小编就为大家带来一篇javascript中去除数组重复元素的实现方法【实例】。小编觉得挺不错的，现在分享给大家，也给大家做个参考，一起跟随小编过来看看吧...2016-04-16

求解旋转数组的最小数字

相关文章

阁下可能感兴趣的内容

推荐阅读