leetcode_find_minimum_in_rotated_sorted_array_ii

发表于

难度：Medium

解题思路：如果遇到重复的，右边的index向前进一步。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMin(vector<int>& nums) {
        return find_min_with_binary(nums,0,nums.size()-1);
    }
    int find_min_with_binary(vector<int> &nums, int left, int right)
    {
        if(left == right)
            return nums[left];
        else if(left+1 == right)
            return min(nums[left],nums[right]);
        int mid = left+(right-left)/2;
        if(nums[mid] < nums[right])
            return  min(nums[mid], find_min_with_binary(nums,left,mid));
        else if(nums[mid] > nums[right])
            return  find_min_with_binary(nums,mid+1,right);
        else
            return find_min_with_binary(nums,left,right-1);
    }
};

运行结果：6ms，超过28.63%