求解旋轉數組的最小數字
題目描述：
把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小數組。例如數組{3,4,5,1,2}是數組{1,2,3,4,5}的旋轉數組，該數組的最小值為1。
思路解析：
O(N)的算法
這種算法的思想就是遍歷這個數組，由于這個數組是兩部分有序的數組，因此遍歷這個數組時當后一個數字小于前一個數字時，則后一個（即較小）一定為整個數組中最小的數字。
這種算法的思想很簡單，但就是時間復雜度較大，因此不是很好的算法。
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)的算法
這種算法思想類似于二分查找，首先每次找到數組中中間的數字mid，如果mid大于最左端left，說明最小數在mid的右側區間，則改變left，置left為mid；如果mid小于數組右側right，說明最小數在mid的左側區間，則改變right為mid….當left的數字小于等于right的數字時，說明已經找到最小數，這個也是循環結束的條件
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];}感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
