AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

LeetCode 154. Find Minimum in Rotated Sorted Array II

作者: 作者的头像   吕德华 ,  2019-07-12 17:58:14 ,  所有人可见 ,  阅读 713


0


**题目描述
现有一个有序数组,假设从某个数开始将它后面的数按顺序放到了数组前面。
(即 [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
**
借y大佬图一用哈
1_92f5550a64-2.png
如上图,此题要进行二分,就必须把右侧与nums[0]相等一段去掉,去掉之后再判断数组是否单调

class Solution//方法一
{
public:
    int findMin(vector<int> &nums)
    {
        int l=0,r=nums.size()-1;
        while(nums[l]==nums[r]&&l<r) r--;//l<r防止元素相等时数组被清空
       if(nums[r]>nums[0]) return nums[0];//判断单调递增
        while(l<r)
        {
            int mid=l+r>>1;
            if(nums[mid]<nums[0]) r=mid;
            else l=mid+1;
        }
        return nums[l];
    }
};
class Solution//方法二
{
public:
    int findMin(vector<int> &nums)
    {
        int l=0,r=nums.size()-1;
        while(nums[l]==nums[r]&&l<r) r--;
       if(nums[r]>nums[0]||r==0) return nums[0];//r==0时排除数组大小为1时,以便二分能进行
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(nums[mid]>=nums[0]) l=mid;
            else r=mid-1;
        }
        return nums[l+1];
    }
};

3 评论


用户头像
秦淮岸灯火阑珊   2019-07-12 18:34         踩      回复

加油!期待更好的分享!

用户头像
吕德华   2019-07-12 21:21         踩      回复

大佬过奖了

用户头像
秦淮岸灯火阑珊   2019-07-12 21:53    回复了 吕德华 的评论         踩      回复

喜欢有图文解释的博客.


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息