leetcode：154. 寻找旋转排序数组中的最小值 II

题目

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
• 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。

进阶：本题与[中等] 153. 寻找旋转排序数组中的最小值类似，但区别是本题的 nums 数组可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

示例：

输入：nums = [1,3,5]
输出：1

输入：nums = [2,2,2,0,1]
输出：0

解答 & 代码

本题与[中等] 153. 寻找旋转排序数组中的最小值类似，但区别是本题的 nums 数组可能包含重复元素

旋转后的数组：最小值所在位置即旋转点

二分查找：对于二分查找的每一步，查找的区间范围为 **[left, right]**，区间中点为 mid，且最小值一定在该区间内，也就是说区间左边界 **left** 一定位于最小值左侧（含最小值处），区间右边界 **right** 一定位于最小值右侧（含最小值处）
比较区间中点元素 **nums[mid]** 和区间右边界元素 **nums[right]** 的值，分为三种情况：

1. **nums[mid] < nums[right]**：说明 mid 位于最小值右侧（含最小值处本身），因此可以忽略当前二分查找区间的右半部分，令 **right = mid**

1. **nums[mid] > nums[right]**：说明 mid 位于最小值左侧，因此可以忽略当前二分查找区间的左半部分，令 **left = mid + 1**

1. **nums[mid] == nums[right]**：因为 nums 数组中存在重复元素，因此无法判断 mid 处于最小值左侧还是右侧，都有可能，因此无法确定该忽略当前二分查找区间的左半部分还是右半部分。但是有一点可以确定，即区间右边界 **num[right]** 可以舍弃，因此令 **right = right - 1**（本题关键所在！）
   1. 假设 num[right] 是最小值，而 nums[mid] == nums[right]，那么 nums[mid] 也是最小值，因此舍弃了 nums[right] 也无所谓
   2. 假设 num[right] 不是最小值，那么自然可以舍弃

最终，当区间长度为 1 （即 **left == right **时），只剩下一个位置，说明该位置（**left** or **right**）就是最小值，可以二分查找。因此二分查找循环的条件是 **while(left < right)**

class Solution {
public:
    int findMin(vector<int>& nums) {
        int len = nums.size();
        int left = 0;
        int right = len - 1;
        // 注意循环条件是 left < right，因为当区间长度为 1 （即 left == right 时），只剩下一个位置，就是最小值的位置
        // 如果硬要携程 left <= right，也可以，只是最后当 left == right 时会多走一步，且需要根据最后这一步考虑最后的返回是 left 还是 right
        while(left < right)        
        {
            int mid = left + (right - left) / 2;
            /* 比较区间中点和区间右边界的元素值*/
            // 1. nums[mid] < nums[right]：说明 mid 位于最小值右侧（含最小值处本身），因此可以忽略当前二分查找区间的右半部分，令 right = mid
            if(nums[mid] < nums[right])
                right = mid;
            // 2. nums[mid] > nums[right]：说明 mid 位于最小值左侧，因此可以忽略当前二分查找区间的左半部分，令 left = mid + 1
            else if(nums[mid] > nums[right])
                left = mid + 1;
            // 3. nums[mid] == nums[right]：无法判断 mid 处于最小值左侧还是右侧，但无论如何区间右边界元素都可以舍弃
            else if(nums[mid] == nums[right])
                --right;        // 本题关键所在！！！！！！！！！
        }
        return nums[left];        
    }
};

复杂度分析：设 nums 数组长为 n

• 时间复杂度：
  • 平均时间复杂度 O(log n)
  • 最坏情况下时间复杂度 O(n)：如果数组中元素全都相同，那么就要执行 n 次
• 空间复杂度 O(1)：

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 87.09% 的用户
内存消耗：11.9 MB, 在所有 C++ 提交中击败了 73.93% 的用户