leetcode: 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.

原问题链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

 

问题分析

　　这个问题和前一个有点不一样的地方在于，它允许里面有重复的元素。这样它里面的情况就稍微有点不一样了。我们还是可以通过原来的方式判断当前段是在哪个部分，只是判断的条件稍微有点变化。这里还存在一种左边的值和中间节点值相等的情况。也可能在数组中间两边节点的值也是相等的。

　　在实现的时候，我们如果发现左边节点值比中间节点值小，说明它是在左边的上升段上，那么这和原来的设定是一样，l = mid + 1。我们取的最小值就不能去看mid后面的值了，而是判断l和min之间更小的那个值。同样对于右边节点值也适用。

　　详细的代码实现如下：

 

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