查找旋转数组的最小值（存在重复）

问题&＃xff1a;

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 an array sorted in ascending order 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.

解决&＃xff1a;

① 本题与I的区别在于翻转数组中可能会存在重复。我们只需要添加一个条件&＃xff0c;它检查最左边的元素和最右边的元素是否相等。 如果是的话&＃xff0c;我们可以简单地放下其中一个。使用递归方法进行处理。

class Solution{ //1ms
    public static int findMin(int[] nums){
        return helper(nums,0,nums.length - 1);
    }
    public static int helper(int[] nums,int left,int right){
        if (left &＃61;&＃61; right){
            return nums[left];
        }
        if (nums[left] >&＃61; nums[right]){
            while(left &＃43; 1                 int mid &＃61; (right - left) / 2 &＃43; left;
                if (nums[left] &＃61;&＃61; nums[right]){
                    return helper(nums,left,right - 1);
                }else if (nums[mid] >&＃61; nums[left] || (nums[mid] nums[right])){
                    return helper(nums,mid,right);
                }else if(nums[mid]                     return helper(nums,left,mid);
                }
            }
            return Math.min(nums[left],nums[right]);
        }
        return nums[left];
    }
}

② 使用迭代方法。

class Solution{//1ms
    public static int findMin(int[] nums) {
        int left &＃61; 0;
        int right &＃61; nums.length - 1;
        while(left &＃43; 1             int mid &＃61; (right - left) / 2 &＃43; left;
            while (nums[left] &＃61;&＃61; nums[right] && left !&＃61; right){
                right --;
            }
            if (nums[left]                 return nums[left];
            }
            if (nums[left] <&＃61; nums[mid] || (nums[left] > nums[mid] && nums[mid] > nums[right])){
                left &＃61; mid;
            }else{
                right &＃61; mid;
            }
        }
        return Math.min(nums[left],nums[right]);
    }
}

③ 直接遍历

class Solution {//1ms
    public int findMin(int[] nums) {
        int min &＃61; Integer.MAX_VALUE;
        for(int i &＃61; 0; i             if(nums[i]                 min &＃61; nums[i];
        }
        return min;
    }
}