核心考點：陣列理解，二分查找，臨界條件
把一個陣列最開始的若干個元素搬到陣列的末尾，我們稱之為陣列的旋轉，輸入一個非遞減排序的陣列的一個旋轉，輸出旋轉陣列的最小元素，例如陣列{3, 4, 5, 1, 2}是陣列{1, 2, 3, 4, 5}的一個旋轉，該陣列的最小值為1，NOTE：給出的所以元素都大于0，若陣列大小為0，請回傳0，
決議一：（不提倡）
尋找陣列當中的最小值，不管怎么說，遍歷一遍陣列當中元素是肯定能找到的，
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if (rotateArray.size() == 0) //陣列大小為0，回傳0
return 0;
int min = rotateArray[0];
//遍歷陣列尋找最小值
for (size_t i = 1; i < rotateArray.size(); i++)
{
if (rotateArray[i] < min)
min = rotateArray[i];
}
return min; //回傳最小值
}
};
決議二：（較提倡）
因為原陣列是一個非遞減的陣列，所以原陣列當中的每一個元素都大于或等于其前面的一個元素，而原陣列經過旋轉后被分為兩部分（一部分是被旋轉到后面的，另一部分是未被旋轉的），這兩部分也分別滿足該規律（每一個元素都大于或等于其前面一個元素），
所以我們可以挨個比較陣列當中相鄰的兩個元素，若前一個元素小于或等于后一個元素，則繼續比較；若前一個元素大于后一個元素，則說明這兩個元素之間就是分界處，此時回傳后一個元素即可，
若是遍歷完陣列都沒有找到前一個元素大于后一個元素的情況，則說明旋轉陣列是由原陣列的全部元素旋轉后得到的（旋轉后的陣列與原陣列相同），此時回傳陣列的第一個元素即為最小值，
該解法找到特定情況后便可以直接回傳陣列當中的最小值，相對于第一種解法來說效率會高一點，但其查找效率的快慢卻決于陣列的旋轉深度，
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if (rotateArray.size() == 0) //陣列大小為0，回傳0
return 0;
for (size_t i = 1; i < rotateArray.size(); i++)
{
if (rotateArray[i - 1] > rotateArray[i]) //找到前一個元素小于后一個元素的情況
return rotateArray[i]; //回傳后者即為最小值
}
return rotateArray[0]; //陣列遍歷結束，回傳陣列的第一個元素即為最小值
}
};
決議三：（正解）
對于該題目，我們還可以使用二分查找的方式：找到陣列的中間元素mid，將mid與某一元素進行比較，確定最小值位于mid的哪一側，從而達到查找一次后待查找元素減半的效果，
這里我們選擇將中間元素mid與陣列的最后一個元素進行比較（也可以選擇將其與第一個元素進行比較），那么會出現以下四種情況：
情況一： left索引的元素小于right索引的元素，
此時說明[left, right]區間內的元素已經是非遞減序列了，left索引的元素便是陣列當中的最小值，
情況二： mid索引的元素小于right索引的元素，
此時說明[mid+1, right]區間內的元素都大于等于mid索引的元素，而mid左側還有可能有比mid索引的元素更小的元素，所以將待查找區間縮小為[left, mid]，
情況三： mid索引的元素大于right索引的元素，
此時說明[left, mid]區間內的元素都大于等于right索引的元素，而在mid和right之間可能有比right索引的元素更小的元素，所以將待查找區間縮小為[mid+1, right]，
情況四： mid索引的元素等于right索引的元素，
此時無法判斷陣列最小值位于mid的哪一側，我們可以選擇將right左移一個位置，然后重新進行判斷，
通過這種方法一直判斷下去，直到出現第一種情況得到最小值，或是直到left和right所確定的區間當中只有一個元素時，這一個元素便是陣列當中的最小值，
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if (rotateArray.size() == 0) //陣列大小為0，回傳0
return 0;
int left = 0, right = rotateArray.size() - 1;
while (left < right)
{
if (rotateArray[left] < rotateArray[right]) //[left,right]區間已經是非遞減序列，回傳區間內第一個元素即可
return rotateArray[left];
int mid = left + (right - left) / 2;
if (rotateArray[mid] < rotateArray[right]) //待查找區間縮小為[left, mid]
{
right = mid;
}
else if (rotateArray[mid] > rotateArray[right]) //待查找區間縮小為[mid+1, right]
{
left = mid + 1;
}
else //mid和right索引的元素值相同，將right往左移
{
right--;
}
}
return rotateArray[left]; //left和right所確定的區間當中只有一個元素，回傳這個元素即可
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/298412.html
標籤：其他