题目

题解

这道题与153题类似，是其进阶，主要是出现了重复元素，因此要加上情况三的判断

  • 如果中间的数小于最右边的数，则右半段是有序的,最小值在左半段；
  • 若中间数大于最右边数，则左半段是有序的，最小值在右半段，
  • 若中间值等于最右值，则将右指针左移一位，去掉一个重复元素
0　　1　　1　　 6　　6　　6　　6

6　　0　　1　　 1　　6　　6　　6

6　　6　　0　　 1　　1　　6　　6

6　　6　　6　　 0　　1　　1　　6

6　　6　　6　　 6　　0　　1　　1

1　　6　　6　　 6　　6　　0　　1

1　　1　　6　 　6　　6　　6　　0
  • 时间复杂度$O(logN)$~$O(N)$
  • 空间复杂度$O(1)$
class Solution {//与#153类似，但是多了重复的元素，还是用二分查找，但是需要在条件判断中多一个中间值等于最右值的选项，空间复杂度为O(logn)~O(n)
public:
    int findMin(vector<int>& nums) {
        int left = 0,right = nums.size()-1;//设置左右指针
        while(left<right){//设置循环的条件
            int mid = left + (right-left)/2;//设置中间值，这种方式防止溢出
            if(nums[mid]<nums[right]) right = mid;//
            else if(nums[mid]>nums[right]) left = mid+1;
            else right--;
        }
        return nums[right];//注意这里要返回右指针的，因为情况一包括了最小值在中间的情况，用右指针可以选到中间。
    }
};