題目描述
把一個數(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着绊。
思路：既然數(shù)組本來是一個非遞減數(shù)組，那么就說明是自小到大順序的熟尉，但不排除有重復(fù)值归露。
經(jīng)過旋轉(zhuǎn)后，第一個數(shù)字作為最小值斤儿，就被放到了最大值的后面剧包，所以當(dāng)遍歷到第 i 個數(shù)字值小于i-1個數(shù)字的值時，說明第i個就是最小值往果。
如果一直沒有找到疆液，說明沒有經(jīng)過旋轉(zhuǎn)，第一個值就是最小值陕贮，默認返回第一個值堕油。
此方法的時間代價是O(n)
缺點：重復(fù)值情況下，沒法發(fā)現(xiàn)重復(fù)值的第一個就是最小值肮之，比如一個數(shù)組為{1掉缺，1，2局骤，3攀圈，4，5峦甩，6}赘来，旋轉(zhuǎn)之后的數(shù)組為{1，2凯傲，3犬辰，4，5冰单，6幌缝，1}，此時第一個值就是最小值诫欠，但是一直對比到最后一個才能輸出1涵卵。
import java.util.ArrayList;
public class Solution {
? ? public int minNumberInRotateArray(int [] array) {
? ? int min = 0;
? ? if(array.length == 0){
? ? return 0;
? ? }
? ? for(int i = 0;i<array.length-1;i++){
? ? if(array[i]>array[i+1]){
? ? min = array[i+1];
? ? break;
? ? }
? ? }
? ? return min;
? ? }
}
