求解旋轉數組的最小數字
題目描述：
把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小數組。例如數組{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];
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
