?一、題目內(nèi)容
?提供一下該OJ題的鏈接：旋轉數(shù)組的最小數(shù)字_?？皖}霸_?？途W(wǎng) (nowcoder.com)
二、題目分析
通過示例1可知，我們寫代碼的目的是在數(shù)組中找到一個最大值，并且返回來；
我們很容易的會想到創(chuàng)建一個變量：int min = 0; 然后遍歷整個數(shù)組，依次比較把一個最小值用該變量接收；但是時間復雜度是O(n)，空間復雜度是O(1),這很顯然不符合題目時間復雜度O(logn)的要求。
通過O(logn)，這個要求，我們由果索因，會想到之前我們經(jīng)常打招呼的二分查找法，其時間復雜度符合O(logn)；但是二分查找的前提是：需要數(shù)組的有序的；
我們?nèi)绻麑λM行排序的話，那最快的排序的時間復雜度至少是O(nlogn)，顯然我們要先排序是不可行的。
我們在仔細回閱問題的描述；發(fā)現(xiàn)這個旋轉數(shù)組也有他的特殊之處：
1.該數(shù)組有兩個子數(shù)組是有序的。且該數(shù)組的最小值一定在數(shù)組的前一個字數(shù)組升序邊界；
2.該數(shù)組的最后一個元素很大概率不屬于我們要找的元素；
于是我們得出了一個類似于二分法（也是用雙指針），但不同于二分法什么時候折半?yún)^(qū)間的考慮
?根據(jù)對上圖的理解：我們就可以知道，這題中的二分法，與之前用的二分法，差別就在于判斷條件。
那有人會問，若下標mid所指向的值 = 下標right所指向的值，該怎么辦？
right-1；縮小范圍；。文章來源：http://www.zghlxwxcb.cn/news/detail-804359.html
三、完整代碼
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
*
* @param nums int整型一維數(shù)組
* @param numsLen int nums數(shù)組長度
* @return int整型
*/
int minNumberInRotateArray(int* nums, int numsLen )
{
int lift = 0;
int right = numsLen-1;
//4 5 6 7 8 9 1 2 3
//8 9 1 2 3
//8 9 1
//1
while(lift<right)
{
int mid = (lift+right)/2;
if(nums[mid]>nums[right])
{
//前邊的一半?yún)^(qū)間可以拋棄；
lift = mid+1;
}
else if(nums[mid]<nums[right])
{
//后別的一半?yún)^(qū)間可以拋棄(不包括mid)；
right = mid;
}
else
{
//往前面走一位；
right -= 1;
}
}
return nums[lift];
}?文章來源地址http://www.zghlxwxcb.cn/news/detail-804359.html
到了這里，關于C 語言每日一題——旋轉數(shù)組的最小數(shù)字的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
