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

问题描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
     思路：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复杂度显然是O(n)。但这个思路没有利用输入数组的特性。既然有时间复杂度更小的算法，我们容易想到二分查找，因为它的时间复杂度为O(logn)。这个问题是否可以运用二分查找呢？答案是肯定的。观察一下数组的特性，首先递增（称为递增a），然后突然下降到最小值，然后再递增（称为递增b）。当然还有一种特殊情况，就是数组递增，中间没有下降，即旋转元素个数为0。
      对于一般的情况，假设A为输入数组，left 和 right 为数组左右边界的坐标，考察中间位置的值A[mid] ，如果A[mid] <= A[right]，表明处于递增b，调整右边界 right = mid；如果A[mid] >= A[left]，表明处于递增a，因此调整左边界left = mid。当左右边界相邻时，较小的一个就是数组的最小值。其实，对于一般情况，右边界所指的元素为最小值。
     对于特殊情况，即旋转个数为0。按照上述算法，右边界会不断减少，直到与左边界相邻。这时左边界所指的元素为最小值。下面给出几组测试案例：

//{1,2,3,4,5,6,7,8,9,10}  1
//{4,5,6,7,8,9,10,1,2,3}  1
//{1,1,1,1,1,1,1,1,1,1}  1
//{1,9,10,1,1,1,1,1,1,1}  1
//{9,9,9,9,9,9,9,10,1,9}  9 错误

第五组的结果是错误的。其实，上述算法适用于严格递增的数组，对于非严格递增，用二分法无法保证正确解。有兴趣的读者，可以试试，对于非严格递增的序列，是否可以用二分法得到正确解。
     参考代码：

//函数功能 ： 旋转数组的最小元素
//函数参数 ： pArray指向数组，len为数组长度
//返回值 ：  最小元素
int FindMin(int *pArray, int len)
{
  if(pArray == NULL || len <= 0)
    return 0;
  int left = 0, right = len - 1, mid;
  while(right - left != 1)
  {
     mid = left + ((right - left)>>1);
     if(pArray[right] >= pArray[mid])
       right = mid;
     else if(pArray[left] <= pArray[mid])
       left = mid;
  }
  return pArray[right] > pArray[left] ? pArray[left]: pArray[right];
}
赞 (0)

相关推荐

  • 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

  • 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++中求旋转数组中的最小数字（经典面试题）

    面试题:旋转数组的最小数字 题目:把一个数组的最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增数组的旋转,输出旋转数组的最小元素.例如数组{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

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

    求解旋转数组的最小数字

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

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

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

  • C语言找出数组中的特定元素的算法解析

    问题描述:一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],其左边的数都小于等于它,右边的数都大于等于它.能否只用一个额外数组和少量其它空间实现.       思路:如果能用两个辅助数组,那么相对来说简单一点,可定义数组Min和数组Max,其中Min[i]表示自a[i]之后的最小值(包括a[i]),Max[i]表示自a[i]之前元素的最大值.有了这两个辅助数组后,对于a[i],如果它大于Max[i-1]并且小于Min[i+1],那么就符合要求.       但是题目要求是只用一个

  • C++实现LeetCode(33.在旋转有序数组中搜索)

    [LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If f

  • C++实现LeetCode(81.在旋转有序数组中搜索之二)

    [LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search.

  • java实现向有序数组中插入一个元素实例

    整理文档,搜刮出一个java实现向有序数组中插入一个元素,稍微整理精简一下做下分享 package cn.jbit.array; import java.util.*; public class Insert { public static void main(String[] args) { //字符排序 char[] chars = new char[9]; chars[0] = 'a'; chars[1] = 'c'; chars[2] = 'u'; chars[3] = 'b'; cha

  • 删除PHP数组中的重复元素的实现代码

    删除PHP数组中的重复元素的实现代码

    我们上一篇文章讲述了<如何删除PHP数组中头部,尾部,任意元素>,本文我们讲述通过 array_unique()函数删除数组中重复元素. array_unique()函数,将数组元素的值作为字符串排序,然后对每个值只保留第一个键名,忽略所有后面的键名,就是删除数组中重复的元素, 语法格式如下: array arry_unique(array array) 参数 array 为输入的数组. 下面实例使 array_unique()函数删除数组中重复的元素,具体示例代码如下: <?php h

  • PHP list() 将数组中的值赋给变量的简单实例

    list() PHP list() 用一步操作把数组中的值赋给一些变量.同 array() 一样,list() 不是真正的函数,而是语言结构. 语法: void list( mixed var, mixed ... )注意: list() 仅能用于数字索引的数组并假定数字索引从 0 开始. 例子1: <?php $arr_age = array(18, 20, 25); list($wang, $li, $zhang) = $arr_age; echo $wang; //输出:18 echo $

  • 利用python查看数组中的所有元素是否相同

    不知道大家有没有过这种经历,就是想要判断两个数组运算后得到的新数组中的各个元素值是否相同.这里给出一种使用np.unique()的方法,代码如下: import numpy as np class Debug: @staticmethod def isAllElementSame(): x1 = np.array([[1, 2, 3], [3, 4, 5], [6, 7, 8]]) x2 = np.array([[81., 162., 243., ], [243., 324., 405.], [

  • java去除已排序数组中的重复元素

    java去除已排序数组中的重复元素

    题目描述 给定一个已排序的数组,去除数组中的重复元素,只保留一个重复的元素,并且返回新的数组长度. 要求: 不要给数组分配额外的空间,你必须使用常量的内存大小进行原地操作. 例如: 给出数组A=[1,1,2],你的函数调用之后必须返回长度length=2,并且A现在变成[1,2]. 输入 一个已排序的数组,例如[1,1,2]. 输出 返回数组新的长度,例如length=2. 快慢指针法 设置fast指针遍历数组,slow指针指向不重复元素的下一位. public static int remov

  • JavaScript去掉数组中的重复元素

    在写程序过程中,经常会遇到去除数组中重复元素的需求.要实现这个功能其实并不难. 我们可以用一个两重循环来实现,对于小的数组,这样做当然并无不妥. 但如果我们的数组比较大,里面的元素有上万个.那么用两重循环,效率是极为低下. 下面我们就用js的特性,编写一个高效去除数组重复元素的方法. 复制代码 代码如下: <script> function unique(data){ data = data || []; var a = {}; for (var i=0; i<data.length;

随机推荐