题目：

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.

链接： 

题解：

find min in rotated sorted array ii， 这道题目是上道题的follow up，包括了数组中有重复数字的情况。主要思路和Search in Rotated Sorted Array一样，可以使用Decision Tree决策树，划分清楚每种条件，然后解题。 这里可以先判定nums[lo] < nums[hi]时，nums[lo]为最小值，接下来根据nums[mid]与nums[hi]的关系来决定并且update min。其实还能再写得简洁一些。

Time Complexity - O(n)，Space Complexity - O(1)。

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

 

测试：