LeetCode_二分搜索_困难_154.寻找旋转排序数组中的最小值 II

雨点打透心脏的1/2处 2023-10-08 19:09 53阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

已知一个长度为 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。**请你找出并返回数组中的最小元素**。

你必须尽可能减少整个过程的操作步骤。

**示例 1：**  
输入：nums = \[1,3,5\]  
输出：1

**示例 2：**  
输入：nums = \[2,2,2,0,1\]  
输出：0

**提示：**  
n == nums.length  
1 <= n <= 5000  
\-5000 <= nums\[i\] <= 5000  
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii

## 2.思路 ##

（1）二分搜索  
本题与[153.寻找旋转排序数组中的最小值][153.]这题类似，只不过本题中的 nums 数组可能包含重复元素。

相关题目：  
[LeetCode\_二分搜索\_中等\_33.搜索旋转排序数组][LeetCode_33.]  
[LeetCode\_二分搜索\_中等\_81.搜索旋转排序数组 II][LeetCode_81._ II]  
[LeetCode\_二分搜索\_中等\_153.寻找旋转排序数组中的最小值][153.]

## 3.代码实现（Java） ##

//思路1————二分搜索
    class Solution {
        
        public int findMin(int[] nums) {
        
            int left = 0;
            int right = nums.length - 1;
            while (left < right) {
        
                int mid = left + (right - left) / 2;
                if (nums[mid] > nums[right]) {
        
                    //如果 nums[mid] > nums[right]，说明最小值在 mid 右侧
                    left = mid + 1;
                } else if (nums[mid] < nums[right]) {
        
                    //如果 nums[mid] < nums[right]，说明最小值在 mid 左侧或者就是 mid 本身
                    right = mid;
                } else {
        
                    //如果 nums[mid] == nums[right]，我们无法判断最小值在 mid 的左侧还是右侧，因此将右边界缩小一位
                    right--;
                }
            }
            return nums[left];
        }
    }

[153.]: https://blog.csdn.net/weixin_43004044/article/details/125652382
[LeetCode_33.]: https://blog.csdn.net/weixin_43004044/article/details/118211776
[LeetCode_81._ II]: https://blog.csdn.net/weixin_43004044/article/details/120010758