小編在求職找找工作期間劍指offer上的算法題刷了很多遍砾淌，并且每道題小編當時都總結(jié)了一種最適合面試時手撕算法的最優(yōu)解法磕蛇∑盗玻考慮到劍指offer算法題在面試中的高頻出現(xiàn)霸褒，小編每天和大家分享一道劍指offer上的算法題司顿，以及小編總結(jié)的答案芒粹。下面是第006道劍指offer算法題：
題目描述
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)免猾。例如是辕，
輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素猎提。
例如获三，數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1锨苏。
NOTE：給出的所有元素都大于0疙教，若數(shù)組大小為0，請返回0伞租。
解析：
見代碼注釋
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array[0]<array[array.length-1]) return array[0];//輸入數(shù)組沒有旋轉(zhuǎn)
int low = 0 ; int high = array.length - 1;
//最小的數(shù)字在旋轉(zhuǎn)之后的第二部分遞增序列中贞谓，所以只需要不斷逼近第二段遞增序列的第一個元素即可
while(low < high){
int mid =(high + low)>>1;
if(array[mid] < array[high]){//[mid,high]屬于第二段遞增序列。所以的往前尋找第二段遞增序列的開頭葵诈，移動high指針
high = mid;
}else if(array[mid] > array[high]){//mid在第一段遞增序列中,high在第二段遞增序列中裸弦，在mid之后尋找第二段遞增序列的開頭
low = mid+1;
}else{//相等無法判斷mid在那個遞增序列中
high--;
}
}
return array[low];
}
//兩個都可以過,這種解法有點奇怪，當數(shù)組有序的時候作喘，應(yīng)該是通不過d
public int minNumberInRotateArray2(int [] array) {
int low = 0 ; int high = array.length - 1;
//最小的數(shù)字在遞減部分理疙，所以只需判斷哪一部分遞減即可
//另外第一部分不遞減，那么第二部分就一定遞減泞坦，鎖以只需要判斷一半即可
while(low < high){
int mid =(high + low) >> 1;
if(array[mid] < array[low]){//如果前半段遞減的話窖贤，最小值在前半段
high = mid;
}else if(array[mid] == array[low]){
low = low + 1;
}else if(array[mid]>array[low]){//這里不好判斷，因為low可能是最小值
low = mid;//這里表示后半段遞減，所以最小值在前半段
}
}
return array[low];
}
}
其他文章
1. 學習筆記和學習資料匯總：前端 + 后端 + java + 大數(shù)據(jù) + python + 100多實戰(zhàn)項目 + C++
2. 我的秋招經(jīng)歷總結(jié)：一站式秋招規(guī)劃
3. 零基礎(chǔ)學爬蟲
歡迎關(guān)注個人公眾號【菜鳥名企夢】赃梧，公眾號專注：互聯(lián)網(wǎng)求職面經(jīng)滤蝠、java、python授嘀、爬蟲物咳、大數(shù)據(jù)等技術(shù)分享：
公眾號菜鳥名企夢后臺發(fā)送“csdn”即可免費領(lǐng)取【csdn】和【百度文庫】下載服務(wù)；
公眾號菜鳥名企夢后臺發(fā)送“資料”:即可領(lǐng)取5T精品學習資料粤攒、java面試考點和java面經(jīng)總結(jié)所森，以及幾十個java、大數(shù)據(jù)項目夯接，資料很全，你想找的幾乎都有
