文章目錄

• 題目理解
• 二分+分治
• 只有二分

154是 153的升級版本。

題目理解

輸入：一個按升序排序的數組nums，但是這個數組在某個位置被旋轉了。(例如., 原始數組是[0,1,2,4,5,6,7]，旋轉后就變成 [4,5,6,7,0,1,2])。注意：這個數組可能包含重復元素。
輸出：這個數組的最小值
要求：O(lgn)時間復雜度
示例1
Input: [3,4,5,1,2]
Output: 1

示例2
Input: [2,2,2,0,1]
Output: 0

示例3

Input: [2,2,2,2,2]
Output: 2

二分+分治

這種思路完全可以按照之前在153的分析實現。在上一個版本的分析中，我們只有在需要判斷一個子數組是否有序的時候使用大小比較：nums[l]<nums[r]。當有重復元素之后，我們還是使用同樣的條件判斷。例如[2,2,0,1,2]這樣的子數組，nums[l]=nums[r]，它是一個無序的。只有nums[l]<nums[r]才能推論得到從l到r是一個有序的子數組。
所以代碼是一樣的。

只有二分

原文鏈接

在標準的二分搜索中會用中間元素與目標值比較：nums[pivot]>target。在這里，中間元素與右邊界元素比較：nums[pivot]與nums[high]。
情況一：nums[pivot]<nums[high]

這個時候子數組從pivot到high是一個有序數組，最小元素出現在左側子數組中。同時，當前中間元素也可能是最小值元素。所以更新high=pivot。

情況二：nums[pivot]>nums[high]

nums[pivot]和最右邊元素不在同一側。一個數組從高到低，一定經歷了最小元素。最小元素在右側子數組中。

情況三：nums[pivot] = nums[high]

如果是圖中case3的情況，最小元素在中間元素的左邊。如果是圖中case3’的情況，則最小元素在中間元素的右邊。這個時候縮小右邊界的范圍：high=high-1。

class Solution {public int findMin(int[] nums) {int l = 0 ,r = nums.length-1;if(nums[r]>nums[l]) return nums[l];while(l<=r){int mid = l+((r-l)>>1);if(nums[mid]<nums[r]){r = mid;}else if(nums[mid]>nums[r]){l = mid+1;}else{r = r-1;}}return nums[l];} }

總結

以上是生活随笔為你收集整理的154. Find Minimum in Rotated Sorted Array II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。