Leetcode154. Find Minimum in Rotated Sorted Array II

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

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

所以我们沿着方法2走

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

现在只剩下$nums[mid]\le nums[r],nums[mid]\le nums[l]$

$[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;$
不能直接排除一半,只能从右往左

那为啥不能是从左往右呢，考虑$[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];}
};