求解旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目描述：
把一個(gè)數(shù)組最開(kāi)始的若干個(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，說(shuō)明最小數(shù)在mid的右側(cè)區(qū)間，則改變left，置left為mid；如果mid小于數(shù)組右側(cè)right，說(shuō)明最小數(shù)在mid的左側(cè)區(qū)間，則改變r(jià)ight為mid….當(dāng)left的數(shù)字小于等于right的數(shù)字時(shí)，說(shuō)明已經(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ì)本站的支持！
新聞熱點(diǎn)
疑難解答
圖片精選
