题目

注意：本题与主站 154 题相同：(https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/)

题解

这道题与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 {
public:
    int minArray(vector<int>& numbers) {
        int left = 0, right = numbers.size()-1;
        while(left<right){
            //定义中间的数
            int mid = left + (right-left)/2;
            //若中间小于右边，说明右半有序，最小值在左半
            if(numbers[mid]<numbers[right]) right = mid;
            //若中间大于右半，说明左半有序，最小值在右半
            else if(numbers[mid]>numbers[right]) left = mid+1;
            //若相等，右指针-1，跳过重复的
            else right--;
        }
        return numbers[right];//注意这里要返回右指针的，因为情况一包括了最小值在中间的情况，用右指针可以选到中间。
    }
};