【leetcode刷題】31.旋轉陣列的最小數字—

?歡迎訂閱《leetcode》專欄，每日一題，每天進步?

什么鬼題目呀，管你旋不旋轉，直接輸出最小值不就完了，，，

——leetcode此題熱評

前言

哈嘍，大家好，我是一條，

糊涂演算法，難得糊涂

考慮再三，也問了大佬，決定還是繼續強化簡單題，

Question

劍指 Offer 11. 旋轉陣列的最小數字

難度：簡單

把一個陣列最開始的若干個元素搬到陣列的末尾，我們稱之為陣列的旋轉，輸入一個遞增排序的陣列的一個旋轉，輸出旋轉陣列的最小元素，例如，陣列 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉，該陣列的最小值為1，

示例 1：
輸入：[3,4,5,1,2]
輸出：1
示例 2：
輸入：[2,2,2,0,1]
輸出：0

Solution

此題的表述比較繞，很多人一遍可能看不懂，其實就像評論說的，最小值就可以了，和旋轉沒關系，

但為了不超時，應該考慮更快的方法，

旋轉陣列：所謂旋轉陣列，有這么幾個點：

一個升序排列的陣列
將前面的一段截下來放到后面
陣列可以分成左排序，右排序，旋轉點幾個部分
左排序都大于右排序
旋轉點就是我們要找的最小值

二分查找：

所以問題由最小值問題轉換為查找旋轉點問題，最快的辦法就是二分查找，

陣列中最特殊的位置是左邊位置 left 和右邊位置 right，將它們與中間位置 mid 的值進行比較，進而判斷最小數字出現在哪里，
注意：不能用左邊與中間比較，舉例：[3, 4, 5, 1, 2] 與 [1, 2, 3, 4, 5]
如果右邊大于中間：說明在左邊，將右端點收縮
如果右邊小于中間：說明在右邊，將左端點收縮

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author yitiaoIT
 */
class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
}