C++中求旋轉(zhuǎn)數(shù)組中的最小數(shù)字（經(jīng)典面試題）
面試題：旋轉(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）當(dāng)輸入的旋轉(zhuǎn)數(shù)組非法時：處理！
（2）當(dāng)輸入的旋轉(zhuǎn)數(shù)組正常時，index1 = 0；index2=length-1：
a:如果arry[index1] <arry[index2]時：說明數(shù)組為原數(shù)組，并沒有進(jìn)行旋轉(zhuǎn)；
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<<"參數(shù)輸入錯誤?。?！"<<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;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
這篇文章主要介紹了利用C++實(shí)現(xiàn)的放煙花程序，用到了EGE圖形庫，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)C++有一定幫助，需要的可以參考一下2022-01-01
在寫Qt應(yīng)用程序時，由于是采用C++語言，經(jīng)常會碰到一個令人棘手的問題，那就是內(nèi)存泄漏，本文主要介紹了Qt下監(jiān)測內(nèi)存泄漏的方法，感興趣的可以了解一下2021-12-12
詳解C++中如何將構(gòu)造函數(shù)或析構(gòu)函數(shù)的訪問權(quán)限定為private
這篇文章主要介紹了詳解C++中如何將構(gòu)造函數(shù)或析構(gòu)函數(shù)的訪問權(quán)限定為private的方法,文中還解釋了構(gòu)造函數(shù)與虛函數(shù)的區(qū)別,需要的朋友可以參考下2016-03-03
本文主要介紹了用VScode編寫C++大型項目的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
這篇文章主要介紹了mfc入門教程，手把手教你如何開發(fā)一個簡單的計算器,需要的朋友可以參考下2019-04-04
C語言結(jié)構(gòu)體(struct)的詳細(xì)講解
C語言中,結(jié)構(gòu)體類型屬于一種構(gòu)造類型(其他的構(gòu)造類型還有：數(shù)組類型,聯(lián)合類型),下面這篇文章主要給大家介紹了關(guān)于C語言結(jié)構(gòu)體(struct)的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-03-03
Sqlite 數(shù)據(jù)庫作為 Qt 項目開發(fā)中經(jīng)常使用的一個輕量級的數(shù)據(jù)庫，可以說是兼容性相對比較好的數(shù)據(jù)庫之一。本文為大家介紹了Qt操作SQLite數(shù)據(jù)庫的具體方法，希望對大家有所幫助2023-03-03
Visual Studio新建類從默認(rèn)internal改為public
本文將介紹如何將Visual Studio中的internal修飾符更改為public,以實(shí)現(xiàn)更廣泛的訪問和重用,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-09-09
這篇文章主要為大家介紹了C++缺省參數(shù)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
C++實(shí)現(xiàn)LeetCode(107.二叉樹層序遍歷之二)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(107.二叉樹層序遍歷之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07