欧博开户:LeetCode 81,在不满足二分的数组内使用二分法 II

admin 5个月前 (07-05) 科技 23 0

本文始发于小我私家民众号:TechFlow,原创不易,求个关注


今天是LeetCode专题第50篇文章,我们来聊聊LeetCode中的81题Search in Rotated Sorted ArrayII。

它的官方难度是Medium,点赞1251,否决470,通过率32.8%。从通过率上来看,这题属于Medium难度当中偏难一些的问题,也简直云云,稍稍有些磨练头脑。

题意

假设我们有一个含有重复元素的有序数组,我们随意选择一个位置将它分成两半,然后将这两个部门换取顺序拼接成一个新的数组。现在给定一个target,要求返回一个bool效果,解释target是否在数组当中

样例

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

若是是你凭据顺序刷LeetCode或者是本专题的话,你会发现我们在之前做过一道异常相似的问题。它就是LeetCode的33题,Search in Rotated Sorted ArrayI。不外差异的是,在33题的题意当中,明确解释了数组当中的元素是不包罗重复元素的,除此之外,这两题的题意完全一样。

LeetCode 33,在不满足二分的数组内使用二分的方式

这么一点小小的差异会带来解法的转变吗?

题解

谜底固然是一定的,否则出题人可以退休了。

问题是,问题出在那里呢?

我们先不着急,先来回忆一下33题中的做法。我们那时使用了一个最简朴的笨设施,就是先通过二分法找到数组截断的位置。然后再通过截断的位置还原出原数组的情形,凭据我们target的巨细,找到它可能存在的位置。

然则在当前这个问题当中,这个思绪走不通了。走不通的缘故原由也很简朴,就是由于重复元素的存在。

举个例子:[1, 3, 1, 1, 1, 1, 1, 1]

当我们举行二分查找的时刻,发现mid是1和left的1相等,我们基本无法判断截断点事实在mid的左侧照样右侧,二分查找也就无从谈起了。

我们固然可以退一步接纳遍历的方式去寻找切分点,然则既然云云,我们为什么不直接去寻找谜底呢?横竖都已经是O(n)的庞大度了。以是这是行不通的,我们想要使得庞大度维持在就必须要寻找其他的路数。

思绪和解法许多时刻不是凭空来的,需要我们对问题举行深入的剖析。在这个问题当中,我们的问题是明确而且简朴的。就是一个换取了部门顺序的有序数组,只是我们不确定的是换取的部门事实有多长。由于我们最终希望通过二分法来寻找谜底,以是我们可以凭据换取的元素是否过半想出两种情形来。

我把这两种情形用图展示出来:

也就是说我们的支解点可能在数组的前半段也可能在后半段,对于这两种情形我们的处置方式是差异的。

我们先看第一种情形,数组的前半段是有序的,后半段存在截断。若是target的局限在前半段当中,我们可以甩掉掉后半段,直接在前半段中举行二分。否则,我们需要舍弃前半段,在后半段当中重复这个历程。我们可以把后半段看成是一个全新的问题,也一样可以分成两种情形,类似于递归一样的往下执行即可。

再来看第二种情形,第二种情形的后半段和第一种情形的前半段是一样的,都是有序的元素,我们直接二分即可。它的前半段和第一种情形的后半段是一样的,我们没法判断,需要继续二分。

也就是说,我们只能在有序的数组举行二分,若是当前数组存在分段,不是整体有序的,那我们就对它举行拆分。拆分之后总能找到有序的部门,若是还找不到就继续拆分。由于分段点只有一个,以是岂论当前的数组什么样,拆分一次之后,一定至少可以找到一段是有序的

想明了这点之后就简朴了,看起来很像是递归,但实际上它的本质仍然是二分。代码并不难写,然则另有一个问题没解决,就是当nums[m] = nums[l]的时刻,我们若何判断是哪一种情形呢?

谜底是没法判断,两种情形都有可能,对于这种情形也没有很好的设施,我想出来的设施是可以将l向右移动一位,相当于甩掉了一个最左侧的数。我们把这些思绪总结总结,代码也就出来了:

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        l, r = 0, len(nums)-1
        while l <= r:
            m = (l + r) >> 1
            if nums[m] == target:
                return True
            
            if nums[l] == nums[m]:
                l += 1
                continue
                
            if nums[l] < nums[m]:
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            else:
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
        return False

总结

到这里,我们关于这道题的题解就竣事了。在问题的最后,出题人给我们留了一个问题,和33题比起来,这题的解法的时间庞大度会有转变吗

表面上看我们一样用到了二分,以是同样是log级的庞大度,问题的庞大度并没有转变。但实际上并不是这样的,我们来看一种最坏的情形,假设数组当中所有的值所有相等。这个时刻二分就不起效果了,最终会退化成O(n)的线性枚举,这样又变成了O(n)的庞大度。固然,在大部门情形下,这并不会发生。以是是算法的最坏庞大度退化成了O(n),平均庞大度依然是O(logN)。

若是喜欢本文,可以的话,请点个关注,给我一点激励,也利便获取更多文章。

本文使用 mdnice 排版

,

UG环球

欢迎进入环球UG官网(UG环球):www.ugbet.us,环球UG官方网站:www.ugbet.net开放环球UG网址访问、环球UG会员注册、环球UG代理申请、环球UG电脑客户端、环球UG手机版下载等业务。

Sunbet声明:该文看法仅代表作者自己,与本平台无关。转载请注明:欧博开户:LeetCode 81,在不满足二分的数组内使用二分法 II

网友评论

  • (*)

最新评论

文章归档

站点信息

  • 文章总数:712
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1137
  • 评论总数:269
  • 浏览总数:18500