【LeetCode】154. Find Minimum in Rotated Sorted Array II 寻找旋转排序数组中的最小值 II（Hard）（JAVA）

题目地址: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

题目描述：

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.

Example 1:

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

Example 2:

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

Note:

• This is a follow up problem to Find Minimum in Rotated Sorted Array.
• Would allow duplicates affect the run-time complexity? How and why?

题目大意

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

说明：

• 这道题是 寻找旋转排序数组中的最小值 的延伸题目。
• 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

解题方法

1. 和上一题类似，只是上一题所有元素都是唯一的，这一题元素可能是重复的
2. 遇到 nums[start] < nums[end] 我们可以直接得出结果
3. 但是遇到 nums[start] == nums[mid] 时，因为可能是 start == mid（这时候 end = start + 1，已经知道 nums[start] >= nums[end]），直接 start++ 即可；如果 start != mid，反正后面还有相同元素，也可以 start++
4. nums[start] < nums[mid]，结果在 [mid + 1, end] 之间
5. nums[start] > nums[mid]，结果在 [start + 1, mid] 之间
6. note: 如果重复元素过多，判断 nums[start] == nums[mid]，我们都是 start++，最后就会变成 O(n) 的时间复杂度

class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            if (start == end) return nums[start];
            if (nums[start] < nums[end]) return nums[start];
            int mid = start + (end - start) / 2;
            if (nums[start] == nums[mid]) {
                start++;
            } else if (nums[start] < nums[mid]) {
                start = mid + 1;
            } else {
                end = mid;
                start++;
            }
        }
        return 0;
    }
}

执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:38 MB,击败了97.67% 的Java用户

欢迎关注我的公众号，LeetCode 每日一题更新