求解旋轉(zhuǎn)數(shù)組的最小數(shù)字
求解旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目描述：
把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小數(shù)組。例如數(shù)組{3,4,5,1,2}是數(shù)組{1,2,3,4,5}的旋轉(zhuǎn)數(shù)組，該數(shù)組的最小值為1。
思路解析：
O(N)的算法
這種算法的思想就是遍歷這個(gè)數(shù)組，由于這個(gè)數(shù)組是兩部分有序的數(shù)組，因此遍歷這個(gè)數(shù)組時(shí)當(dāng)后一個(gè)數(shù)字小于前一個(gè)數(shù)字時(shí)，則后一個(gè)（即較小）一定為整個(gè)數(shù)組中最小的數(shù)字。
這種算法的思想很簡(jiǎn)單，但就是時(shí)間復(fù)雜度較大，因此不是很好的算法。
int minNumberInRotateArray(vector<int> rotateArray)
{
if (rotateArray.empty())
return -1;
unsigned int i=0;
for (; i<rotateArray.size()-1; i++)
{
if (rotateArray[i] > rotateArray[i+1])
break;
}
return rotateArray[i+1];
}
O(logN)的算法
這種算法思想類似于二分查找，首先每次找到數(shù)組中中間的數(shù)字mid，如果mid大于最左端left，說明最小數(shù)在mid的右側(cè)區(qū)間，則改變left，置left為mid；如果mid小于數(shù)組右側(cè)right，說明最小數(shù)在mid的左側(cè)區(qū)間，則改變r(jià)ight為mid….當(dāng)left的數(shù)字小于等于right的數(shù)字時(shí)，說明已經(jīng)找到最小數(shù)，這個(gè)也是循環(huán)結(jié)束的條件
int minNumberInRotateArray(vector<int> rotateArray)
{
if (rotateArray.empty())
return -1;
unsigned int left=0;
unsigned int right=rotateArray.size()-1;
unsigned int mid=left;
while (rotateArray[left] >= rotateArray[right])
{
if (right-left == 1)
{
mid = right;
break;
}
mid = left+((right-left)>>1);
if (rotateArray[mid]==rotateArray[left] && rotateArray[right]==rotateArray[mid])
return rotateArray[mid];
if (rotateArray[mid] >= rotateArray[left])
left = mid;
else if (rotateArray[mid] <= rotateArray[right])
right = mid;
}
return rotateArray[mid];
}
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
本篇文章是對(duì)C++父類子類中虛函數(shù)的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
本文主要介紹了C++中map和set的簡(jiǎn)介及使用詳解，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
C++ ffmpeg硬件解碼的實(shí)現(xiàn)方法
這篇文章主要介紹了C++ ffmpeg硬件解碼的實(shí)現(xiàn)，對(duì)FFmpeg多媒體解決方案中的視頻編解碼流程進(jìn)行研究。為嵌入式多媒體開發(fā)提供參考，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
野指針就是指針指向的不是一個(gè)有效（合法）的地址,本文主要介紹了C++野指針的具體實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-03-03
C語言編程中分配內(nèi)存空間的相關(guān)函數(shù)
這篇文章主要介紹了C語言編程中分配內(nèi)存空間的相關(guān)函數(shù),分別是malloc()函數(shù)和calloc()函數(shù),需要的朋友可以參考下2015-08-08
這篇文章主要為大家詳細(xì)介紹了C語言之if語句的使用，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
本文主要介紹了C語言#define預(yù)處理宏定義，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
這篇文章主要為大家詳細(xì)介紹了C語言三子棋小游戲的實(shí)現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
實(shí)現(xiàn)緊湊存取，不是按一個(gè)字節(jié)一個(gè)字節(jié)地存取，而是按位存取，本文就是介紹了如何在C++中實(shí)現(xiàn)按位存取,需要的朋友可以參考下2015-07-07
C++實(shí)現(xiàn)教職工管理系統(tǒng)課程設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)教職工管理系統(tǒng)課程設(shè)計(jì)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03