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[index1] >= arry[index2]时，middle = （index1+index2）/2：

       b.1如果arry[index1] >arry[middle],index2 = middle;
       b.2如果arry[index1] <= arry[middle],index1 = middle;
       b.3 如果arry[index1] = arry[middle] = arry[index2],遍历找到最小值。

代码：

Min_RotateArray.hpp

#pragma once 
#include<iostream> 
using namespace std; 
 
int Min_RotateArray(int arry[],int size) 
{ 
  if(arry == NULL || size <= 0) 
  {cout<<"参数输入错误！！！"<<endl;} 
  int min = 0; 
  int index1 = 0; 
  int index2 = size-1; 
  int middle = (index1+index2)/2; 
  if(arry[0] < arry[size-1]) 
    return arry[0]; 
  while(arry[index1] >= arry[index2]) 
  { 
    if(index2-index1 == 1) 
    { 
      min=index2; 
      break; 
       
    } 
    middle = (index1+index2)/2; 
    if(arry[index1] <= arry[middle])//arry[middle]还在第一个递增序列中 
    { 
      index1 = middle; 
    } 
    else             
    { 
      if(arry[index1] >= arry[middle])//arry[middle]在第二个递增序列中 
      {index2 = middle;} 
       
      if(arry[index1] == arry[index2] && arry[index1] == arry[middle]) 
      { 
        for(int i=0;i<size;++i) 
        { 
          if(arry[min]>arry[i]) 
            { 
              min = i; 
              break; 
            } 
        } 
 
      } 
    } 
  } 
  return arry[min]; 
}

Min_RotateArray.cpp

#include"Min_RotateArray.hpp" 
 
int main() 
{ 
  int arry[] = {3,4,5,1,2}; 
  int size = sizeof(arry)/sizeof(arry[0]); 
  int min = Min_RotateArray(arry,size); 
  cout<<"The min is:"<<min<<endl; 
  system("pause"); 
  return 0; 
}

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

# C++中求旋转数组中的最小数字 # 求旋转数组中的最小数字实例代码 # C++实现数组中元素组合出最大值 # C++实现从数组中同时取出最大最小元素算法示例 # 带你了解C++的数组与函数 # c++ 求数组最大最小值函数的实现 # 第一个 # 还在 # 遍历 # 希望能 # 第二个 # 谢谢大家 # 搬到 # 值为 # 若干个 # 称之为 # 最小值 # 面试题 # middle # lt # gt # hpp # Min_RotateArray # pre # strong # br

返回目录在线咨询

上一篇：如何处理Go goroutine中的未捕获错误_Go goroutine Error处理方法
下一篇：唐山玉田铭万技术建站：企业网站的安全防护措施有哪些？

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

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

您的项目需求