154 - Find Minimum in Rotated Sorted Array II

Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Hide Tags

Array Binary Search

Hide Similar Problems

(M) Find Minimum in Rotated Sorted Array

就是在153的基础上，加上过滤重复的值。

刚开始想的是，从mid向两边过滤，发现不能解决问题，

所以换个方向，从start 和 end 向中间过滤，

这样避免了mid的值等于start或者end的值，搞定。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int rst;
        find(nums, 0, nums.size()-1, rst);
        return rst;
    }

    void find(vector<int>& nums, int start, int end, int& min)
    {
        if(start>end)
            return;

        //in case duplicated value
        while((start<end)&&(nums[start] == nums[start+1]))
            start++;

        while((start<end)&&(nums[end] == nums[end-1]))
            end--;

        int mid = (start+end)/2;
        int last = (start<mid)?(mid-1):end;
        int next = (end>mid)?(mid+1):start;

        if((start==end)||(nums[mid]<nums[last]))
            min = nums[mid];
        else if(nums[mid]<nums[end])
            find(nums, start, last, min);
        else
            find(nums, next, end, min);
        return;
    }   
};

8 ms.