Description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

• [4,5,6,7,0,1,4] if it was rotated 4 times.
• [0,1,4,4,5,6,7] if it was rotated 7 times.
  Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Examples

Example 1:

Input: nums = [1,3,5]
Output: 1

Example 2:

Input: nums = [2,2,2,0,1]
Output: 0

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums is sorted and rotated between 1 and n times.

思路

大体上和 #153 是一样的思路，区别在于增加了一个step++步骤
也就是当nums[start] == nums[end]的时候，将start向右移动，直到nums[start] != nums[end]，再执行原来的递归操作

代码

class Solution {
    public int min(int[] nums, int start, int end){
        int end_num = nums[end];
        int i;
        for(i = start; i < end; i++)
            if(nums[i] != end_num)
                break;
        start = i;
        if(start >= end)
            return nums[start];
        
        int mid = (start + end) / 2;
        
        if(nums[start] < nums[end] || nums[start] > nums[mid])
            return min(nums, start, mid);
        else
            return min(nums, mid + 1, end);
    }
    public int findMin(int[] nums) {
        int len = nums.length - 1;
        return min(nums, 0, len);
    }
}