Leetcode154. Find Minimum in Rotated Sorted Array II

Minimum in Rotated Sorted Array II"/>

Leetcode154. Find Minimum in Rotated Sorted Array II

旋转数组找最小，这次值可以重复
不妨假设你已经做了上一题，题解

上一题的方法1肯定是用不了了，因为不再能完全分成2个不同的部分

所以我们沿着方法2走

如果 > n u m s [ r ] >nums[r] >nums[r]，我们依然可以找右半边
如果 n u m s [ l ] < n u m s [ m i d ] < n u m s [ r ] nums[l] < nums[mid] < nums[r] nums[l]<nums[mid]<nums[r],那可以直接返回 n u m s [ l ] nums[l] nums[l]
只能是情况1，不可能是情况2和3

现在只剩下 n u m s [ m i d ] ≤ n u m s [ r ] , n u m s [ m i d ] ≤ n u m s [ l ] nums[mid] \le nums[r], nums[mid] \le nums[l] nums[mid]≤nums[r],nums[mid]≤nums[l]

[ 3 , 3 , 3 , 3 , 1 , 3 , 3 ] n u m s [ l ] = n u m s [ m i d ] = n u m s [ r ] = 3 [3, 3, 3, 3, 1, 3, 3]\ nums[l] = nums[mid] =nums[r] =3 [3,3,3,3,1,3,3] nums[l]=nums[mid]=nums[r]=3
[ 3 , 3 , 1 , 3 , 3 , 3 , 3 ] n u m s [ l ] = n u m s [ m i d ] = n u m s [ r ] = 3 ; [3, 3, 1, 3, 3, 3, 3]\ nums[l] = nums[mid] =nums[r] =3; [3,3,1,3,3,3,3] nums[l]=nums[mid]=nums[r]=3;
不能直接排除一半,只能从右往左

那为啥不能是从左往右呢，考虑 [ 0 , 1 ] [0,1] [0,1]
因为总体是一个单调递增的感觉，从左往右可能g了

class Solution {
public:int findMin(vector<int>& nums) {int l = 0, r = nums.size() - 1;while(l < r){int mid = l + (r - l) / 2;if(nums[mid] > nums[r]){l = mid + 1;}else if(nums[l] < nums[mid]){return nums[l];}else{ // nums[l] <= nums[mid] <= nums[r]// [3, 3, 3, 3, 1, 3, 3] nums[l] = nums[mid] =nums[r] =3;// [3, 3, 1, 3, 3, 3, 3] nums[l] = nums[mid] =nums[r] =3;// cannot decide left or right--r;}}return nums[l];}
};