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.

这道题目是[url] Find Minimum in Rotated Sorted Array[/url]的follow up, 唯一不同的是数组中多了重复元素。这时我们进行比较的时候就会出现相等的情况，如果相等我们就没法判断最小值是在哪半部分，我们只需要加一个相等时的处理，让左指针向前移动一个位置或右指针向后移动一个位置，直到找到不相等的两个元素，这样最坏的情况下就是元素都相等，时间复杂度为O(n)。代码如下：

public class Solution {
    public int findMin(int[] nums) {
        if(nums == null || nums.length == 0) 
            return -1;
        int l = 0;
        int r = nums.length - 1;
        while(l < r) {
            int m = l + (r - l) / 2;
            if(nums[m] > nums[r]) {
                l = m + 1;
            } else if(nums[m] < nums[r]) {
                r = m;
            } else {
                r --;
            }
        }
        return nums[l];
    }
}