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

约定不等于承诺〃 2022-11-08 11:53 146阅读 0赞

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

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

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

请找出其中最小的元素。

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

## 示例 1： ##

输入: [1,3,5]
    输出: 1

## 示例 2： ##

输入: [2,2,2,0,1]
    输出: 0

## 题解 ##

官方最详细：  
[https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-de-zui–16/][https_leetcode-cn.com_problems_find-minimum-in-rotated-sorted-array-ii_solution_xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-de-zui_16]

## 代码 ##

class Solution { 
    public:
        int findMin(vector<int>& nums) { 
    
            int start=0,end=nums.size()-1;
            while(start<=end)
            { 
                int mid=(end+start)/2;
                if(nums[mid]<nums[end])
                { 
                    end=mid;
                }
                // 右边已经排好序
                else if(nums[mid] > nums[end])
                { 
                    start=mid+1;
                }
                else   // 左边已经排好序
                { 
                    end--;
                }
              
            }
            return nums[start];
    
        }
    };

[https_leetcode-cn.com_problems_find-minimum-in-rotated-sorted-array-ii_solution_xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-de-zui_16]: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-de-zui--16/