前言
哈喽，大家好，我是一條。
糊塗算法，難得糊塗
考慮再三，也問了大佬，決定還是繼續強化簡單題。
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];
}
} Result
複雜度分析
時間複雜度：O(logn)
🌈尋寶
⭐今天是堅持刷題更文的第31/100天
⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力
⭐更多算法題歡迎關注專欄《leetcode》
為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等
大家可以先自己找一下擷取方式，尋寶遊戲現在開始。
如果實在找不到可以評論區留言或私信我領取，不過一定要先關注哦！不然無法發私信！