Leetcode 154 Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed? Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

153的改进版,可能会有重复的数字出现,

所以需要单独讨论等于的情况,等于时上界下移,

这样在数字全部相同时会退化为O(n)复杂度

class Solution {  
public:  
    int findMin(vector<int>& nums) {  
        int l = 0, r = nums.size()-1;  
        while(l<r)  
        {  
            int mid = (l + r) >> 1;  
            if(nums[mid] > nums[r])   
                l = mid+1;  
            else if(nums[mid] < nums[r])   
                r = mid;   
            else
                r--;
        }  
        return nums[l];  
    }  
};  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1

842
来自专栏行者常至

003.python科学计算库pandas(上)

版权声明:本文为博主原创文章,允许转载,请标明出处。 https://blog.csdn.net/qwdafedv/article/deta...

912
来自专栏Java爬坑系列

你不可不知的Java引用类型之——弱引用

弱引用是使用WeakReference创建的引用,弱引用也是用来描述非必需对象的,它是比软引用更弱的引用类型。在发生GC时,只要发现弱引用,不管系统堆空间是否足...

2542
来自专栏java 成神之路

Java中的四种引用类型

35712
来自专栏idba

了解Python装饰器

一 装饰器是什么 装饰器是一个用于封装函数或者类的代码工具,显式地将封装器作用于函数或者类上,达到程序运行时动态增加功能的目的。对于函数运行前处理常见前置条件...

1046
来自专栏技术碎碎念

LeetCode-1- Two Sum

Given an array of integers, return indices of the two numbers such that they add...

2948
来自专栏Astropeak

掌握Python 装饰器,其实只需要一盏茶的功夫

1563
来自专栏cloudskyme

设计模式(3)-装扮你的类(装饰模式)

首先看看书上的例子吧!人穿衣服的例子! 类图就不画了,就是简单的类结构。 代码如下: #include <iostream> using namespace ...

2625
来自专栏算法修养

ZOJ 1648 Circuit Board(计算几何)

Circuit Board Time Limit: 2 Seconds Memory Limit: 65536 KB On the circu...

2013
来自专栏C语言及其他语言

[每日一题]C语言程序设计教程(第三版)课后习题6.1

题目描述 输入两个正整数m和n,求其最大公约数和最小公倍数。 输入 两个整数 输出 最大公约数,最小公倍数 样例输入 5 7 样例输出 1 35 提示 此类题目...

3153

扫码关注云+社区

领取腾讯云代金券