求解旋转数组的最小数字

求解旋转数组的最小数字

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小数组。例如数组{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];
}

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

赞 (0)

相关推荐

  • C++中求旋转数组中的最小数字（经典面试题）

    面试题:旋转数组的最小数字 题目:把一个数组的最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增数组的旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1. 算法: (1)当输入的旋转数组非法时:处理! (2)当输入的旋转数组正常时,index1 = 0:index2=length-1: a:如果arry[index1] <arry[index2]时:说明数组为原数组,并没有进行旋转:    b:如果arry[ind

  • java旋转二维数组实例

    本文实例讲述了java旋转二维数组的操作,分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: package test; /*  *     1    2    3    4    5     *    16    17    18    19    6     *    15    24    25    20    7     *    14    23    22    21    8     *    13    12    11    10    9  *  *    写一

  • C++实现旋转数组的二分查找

    本文实例讲述了C++实现旋转数组的二分查找方法,分享给大家供大家参考.具体方法如下: 题目要求: 旋转数组,如{3, 4, 5, 1, 2}是{1, 2, 3, 4, 5}的一个旋转,要求利用二分查找查找里面的数. 这是一道很有意思的题目,容易考虑不周全.这里给出如下解决方法: #include <iostream> using namespace std; int sequentialSearch(int *array, int size, int destValue) { int pos

  • C语言输出旋转后数组中的最小数元素的算法原理与实例

    问题描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个排好序的数组的一个旋转,输出旋转数组的最小元素.例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1.      思路:这道题最直观的解法并不难.从头到尾遍历数组一次,就能找出最小的元素,时间复杂度显然是O(n).但这个思路没有利用输入数组的特性.既然有时间复杂度更小的算法,我们容易想到二分查找,因为它的时间复杂度为O(logn).这个问题是否可以运用二分查找呢?答

  • 求解旋转数组的最小数字

    求解旋转数组的最小数字

    求解旋转数组的最小数字 题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出旋转数组的最小数组.例如数组{3,4,5,1,2}是数组{1,2,3,4,5}的旋转数组,该数组的最小值为1. 思路解析: O(N)的算法 这种算法的思想就是遍历这个数组,由于这个数组是两部分有序的数组,因此遍历这个数组时当后一个数字小于前一个数字时,则后一个(即较小)一定为整个数组中最小的数字. 这种算法的思想很简单,但就是时间复杂度较大,因此不是很好的算

  • 面试题:Java 实现查找旋转数组的最小数字

    在算法面试中,面试官总是喜欢围绕链表.排序.二叉树.二分查找来做文章,而大多数人都可以跟着专业的书籍来做到倒背如流.而面试官并不希望招收的是一位记忆功底很好,但不会活学活用的程序员.所以学会数学建模和分析问题,并用合理的算法或数据结构来解决问题相当重要. 面试题:打印出旋转数组的最小数字 题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素.例如数组 {3,4,5,1,2} 为数组 {1,2,3,4,5} 的一个旋转,该

  • Python划分数组为连续数字集合的练习

    目录 1.问题描述 2.解决方案 3.结语 本文转自微信公众号:"算法与编程之美" 1.问题描述 给你一个整数数组 nums 和一个正整数 k,请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合. 如果可以,请返回 True:否则,返回 False. 示例 1: 输入:nums = [1,2,3,3,4,4,5,6], k = 4 输出:true 解释:数组可以分成 [1,2,3,4] 和 [3,4,5,6]. 示例 2: 输入:nums = [3,2,1,2,3,4,3

  • C++实现LeetCode(189.旋转数组)

    [LeetCode] 189. Rotate Array 旋转数组 Given an array, rotate the array to the right by k steps, where k is non-negative. Example 1: Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate

  • C语言双指针多方法旋转数组解题LeetCode

    C语言双指针多方法旋转数组解题LeetCode

    目录 暴力思路 外加数组 格局抬高 环形替代 LeetCode题目如下: 首先这个中等难度我是没搞懂,后面才发现原来中等中在要求多方法上,那就来看看怎么搞定他吧. 暴力思路 首先我说一下我本人的思路,就是函数进行倒序操作,分三步: 1.整体倒序 :1234567-------7654321 2.前半部分倒序:7654321------- 5674321 3.后半部分倒序:5674321-------5671234 由于题目已经给出了我们 k 的值,我们直接暴力思路(注意是暴力思路非暴力求解),双

  • C#将字节数组转换成数字的方法

    本文实例讲述了C#将字节数组转换成数字的方法.分享给大家供大家参考.具体实现方法如下: // Create a decimal from a byte array public static decimal ByteArrayToDecimal (byte[] src) { // Create a MemoryStream containing the byte array using (MemoryStream stream = new MemoryStream(src)) { // Crea

  • js求数组中全部数字可拼接出的最大整数示例代码

    前言 最近在工作碰到一个问题,就是用javascript求数组中所有数字能拼接出的最大整数,数组的每一项为单独的拼接项,不能再拆开,例如[2,34]中2和34分别为要被拼接的数字,而不是说34还能继续拆分为3和4. 具体需求为,将[7,321,35,4]拼接为7435321.下面话不多说了,来一起看看详细的实现方法吧. 我设计的算法如下: function insertSort(arr) { let res = [arr[0]]; for (let i = 1, len = arr.length

  • PHP重置数组为连续数字索引的几种方式总结

    比如这样的一个php数组: $arr = array( 1 => 'apple', 3 => 'banana', 5 => 'orange' ); 想要转换为这样的数组: $arr = array( 0 => 'apple', 1 => 'banana', 2 => 'orange' ); 1.推荐的方式 array_values 方法 这样方式无论对普通数组还是关联数组都适用 <?php $arr = array( 1 => 'apple', 3 =>

随机推荐