leetCode-154:Find Minimum in Rotated Sorted Array II

问题描述

给定一个升序的整形数组，数组中包含重复数字，要求找出数组中最小的数字。题目链接：**点我**

样例输入输出

输入：[1,3,5]

输出：1

输入：[2,2,2,0,1]

输出：0

问题解法

此题跟 LeetCode-153 类似，只不过此处在数组中加入了重复元素。做法跟原先也差不多，只需要在进行二分查找前对重复元素进行排除处理即可。代码如下

class Solution
{
    public int findMin(int[] nums)
    {
        if (nums[0] < nums[nums.length - 1])
        {
            return nums[0];
        }

        int start = 0;
        int end = nums.length - 1;
        while (start + 1 != end && start < end)
        {
            while (start < end && nums[start] == nums[start + 1])
            {
                start++;
            }

            while (start < end && nums[end] == nums[end - 1])
            {
                end--;
            }
            
            // 先判断一下跳出循环，避免在计算 middle 时将 middle 变成了 start，从而遗漏元素
            if (start + 1 == end)
            {
                break;
            }

            int middle = (start + end) / 2;
            if (nums[start] < nums[middle])
            {
                start = middle;
            }
            else
            {
                end = middle;
            }
        }

        return Math.min(nums[start], nums[end]);
    }
}