导航：首页 > 互联网科技 >

c++怎么实现旋转数组最小数字

发表于：2024-12-03 作者：千家信息网编辑

千家信息网最后更新 2024年12月03日，这篇文章主要介绍了c++怎么实现旋转数组最小数字的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇c++怎么实现旋转数组最小数字文章都会有所收获，下面我们一起来看看吧。题目：

千家信息网最后更新 2024年12月03日c++怎么实现旋转数组最小数字

这篇文章主要介绍了c++怎么实现旋转数组最小数字的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇c++怎么实现旋转数组最小数字文章都会有所收获，下面我们一起来看看吧。

题目：把一个数组最开始的若干元素搬到数组的末尾，称之为数组的旋转。

输入：一个递增排序的数组的一个旋转，

输出：旋转数组的最小元素。

例：数组{3,4,5,1,2}是{1,2,3,4,5}的一个旋转，该数组的最小值为1.

分析：

1）旋转之后的数组可以划分为两个排序的子数组，而且前面子数组的元素都大于后等于后面子数组的元素。

2）最小的元素是这两个字数组的分界线。在排序的数组中，可以使用二分查找法（Ologn）

3)特例，当两个指针指向的数字及他们中间的数字三者相同的时候，无法判定中间的数字是位于前面的子数组还是后面的子数组，即无法移动两个指针来缩小查找范围。此时应采用顺序查找。

int Min(int* numbers,int length){    if(numbers==nullptr||length<=0)        throw new std::exception('invalid parameters')    int index1=0;//子数组1指针    int index2=length-1;//字数组2指针    int indexMid=index1;    while(numbers[index1]>=numbers[index2]){
        if(index2-idnex1==1)//两个指针相邻在一起时，指针2就是最小值        {
            indexMid=index2;            break;        }        indexMid=(index1+index2)/2;                //如果下表为index1/index2/indexMid指向三个数都相同，则顺序查找        if(numbers[index1]==numbers[indexMid]&&numbers[indexMid]==numbers[index2])            return MinInOrder(numbers,index1,index2);        if(numbers[indexMid]>=numbers[index1])            index1=indexMid;        else if(numbers[idnexMid]<=nubmers[index2])            index2=indexMid;    }return numbers[indexMid];}

//顺序排序int MinInOrder(int* numbers,int index1,int index2){
    int result=numbers[index1];    for(int i=index1+1;i<=index2;++i)    {      if(result>numbers[i])result=numbers[i];
    }    return result;
}