大家好，我是小魔龍，Unity3D軟體工程師，VR、AR，虛拟仿真方向，不定時更新軟體開發技巧，生活感悟，覺得有用記得一鍵三連哦。
一、題目
1、算法題目
“給定一個數組，按照升序排列，經過1-n次旋轉後，得到輸入數組，找出數組中最小元素。”
題目連結：
來源：力扣（LeetCode）
連結： 154. 尋找旋轉排序數組中的最小值 II - 力扣（LeetCode）
2、題目描述
已知一個長度為 n 的數組，預先按照升序排列，經由 1 到 n 次 旋轉 後，得到輸入數組。例如，原數組 nums = [0,1,4,4,5,6,7] 在變化後可能得到： 若旋轉 4 次，則可以得到 [4,5,6,7,0,1,4] 若旋轉 7 次，則可以得到 [0,1,4,4,5,6,7] 注意，數組 [a[0], a[1], a[2], ..., a[n-1]] 旋轉一次 的結果為數組 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
給你一個可能存在 重複 元素值的數組 nums ，它原來是一個升序排列的數組，并按上述情形進行了多次旋轉。請你找出并傳回數組中的 最小元素 。
你必須盡可能減少整個過程的操作步驟。
示例 1：
輸入： nums = [1,3,5]
輸出： 1 複制
示例 2：
輸入： nums = [2,2,2,0,1]
輸出： 0 複制
二、解題
1、思路分析
這道題是153題尋找旋轉排序數組中的最小值的更新款，153題也是翻轉數組，找出最小值，154題的不同的地方在于數組中有重複的元素。
153題使用的二分查找，這道題也可以使用二分查找來接替。
也就是找到一個中位數，中位數的一邊是有序的，将有序數組的最小值與目前儲存的最小值比較，繼續二分周遊找中位數，直到左指針大于右指針。
當二分查找結束時，就得到了最小值所在的位置。
2、代碼實作
代碼參考：
class Solution {
public int findMin(int[] nums) {
int low = 0;
int high = nums.length - 1;
while (low < high) {
int pivot = low + (high - low) / 2;
if (nums[pivot] < nums[high]) {
high = pivot;
} else if (nums[pivot] > nums[high]) {
low = pivot + 1;
} else {
high -= 1;
}
}
return nums[low];
}
} 複制
3、時間複雜度
時間複雜度：O(n)
其中n是數組的長度，在二分查找中大部分情況會忽略一半的區間，但是有重複元素那麼循環就會執行n次，每次忽略區間的右端點，時間複雜度為O(n)。
空間複雜度：O(1)
隻需要常量級的空間儲存變量。
三、總結
這道題有重複的元素時間複雜度O(n)，空間複雜度O(1)。
153題沒有重複元素的時候，時間複雜度O(log n)，空間複雜度O(1）。
那麼為什麼多了重複元素就變成O(n)的時間複雜度呢。
因為，二分的本質是二段性，沒有重複元素就可以找到中位點然後二分再查找。
有了重複元素後，就意味着無法直接根據數組中的元素大小關系将數組劃分為兩段。