c++怎么實現(xiàn)旋轉(zhuǎn)數(shù)組最小數(shù)字

發(fā)布時間：2022-03-22 15:44:10 來源：億速云閱讀：111 作者：iii 欄目：互聯(lián)網(wǎng)科技

這篇文章主要介紹了c++怎么實現(xiàn)旋轉(zhuǎn)數(shù)組最小數(shù)字的相關(guān)知識，內(nèi)容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇c++怎么實現(xiàn)旋轉(zhuǎn)數(shù)組最小數(shù)字文章都會有所收獲，下面我們一起來看看吧。

題目：把一個數(shù)組最開始的若干元素搬到數(shù)組的末尾，稱之為數(shù)組的旋轉(zhuǎn)。

輸入：一個遞增排序的數(shù)組的一個旋轉(zhuǎn)，

輸出：旋轉(zhuǎn)數(shù)組的最小元素。

例：數(shù)組{3,4,5,1,2}是{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1.

分析：

1）旋轉(zhuǎn)之后的數(shù)組可以劃分為兩個排序的子數(shù)組，而且前面子數(shù)組的元素都大于后等于后面子數(shù)組的元素。

2）最小的元素是這兩個字數(shù)組的分界線。在排序的數(shù)組中，可以使用二分查找法（Ologn）

3)特例，當兩個指針指向的數(shù)字及他們中間的數(shù)字三者相同的時候，無法判定中間的數(shù)字是位于前面的子數(shù)組還是后面的子數(shù)組，即無法移動兩個指針來縮小查找范圍。此時應(yīng)采用順序查找。

int Min(int* numbers,int length){    if(numbers==nullptr||length<=0)        throw new std::exception('invalid parameters')    int index1=0;//子數(shù)組1指針    int index2=length-1;//字數(shù)組2指針    int indexMid=index1;    while(numbers[index1]>=numbers[index2]){
        if(index2-idnex1==1)//兩個指針相鄰在一起時，指針2就是最小值        {
            indexMid=index2;            break;        }        indexMid=(index1+index2)/2;                //如果下表為index1/index2/indexMid指向三個數(shù)都相同，則順序查找        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;
}

關(guān)于“c++怎么實現(xiàn)旋轉(zhuǎn)數(shù)組最小數(shù)字”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對“c++怎么實現(xiàn)旋轉(zhuǎn)數(shù)組最小數(shù)字”知識都有一定的了解，大家如果還想學習更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道。

向AI問一下細節(jié)

c++怎么實現(xiàn)旋轉(zhuǎn)數(shù)組最小數(shù)字

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標簽