龙空技术网

「Leetcode刷题」「4」寻找两个正序数组的中位数

1G码农 182

前言:

目前各位老铁们对“数组中位数 leetcode”都比较着重,各位老铁们都需要了解一些“数组中位数 leetcode”的相关资讯。那么小编在网摘上网罗了一些对于“数组中位数 leetcode””的相关资讯,希望咱们能喜欢,兄弟们快快来了解一下吧!

题目比较复杂

传送门:

# leetcode submit region begin(Prohibit modification and deletion)"""一种特殊的二分"""from typing import *import queueclass Solution:    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:        if len(nums1) > len(nums2):            # 保证nums1比nums2短            nums1, nums2 = nums2, nums1        m = len(nums1)        n = len(nums2)        print("m=",m)        print("n=",n)        # cut割,即可以割在一个数上,也可以割在两数中间。        #我们定义LMax= Max(LeftPart),RMin = Min(RightPart)        cut1 = 0        cut2 = 0        # l1:max(nums1_left_part); r1:min(nums1_right_part)        cut1Left = 0 # 数组1割的左半部分的尾巴,cut1Left        cut1Right = 0 # 数组1割在右半部分的头。cut1Right        cut2Left = 0 # cut2Left        cut2Right = 0 # cut2Right        # 假设数组长度m小于n,这样是为了算法复杂度在log(min(m,n)),有了假设方便一些        left, right = 0, m*2        #### 暂时没有加入了#,a的长度变成了2m+1        # 二分        while left <= right:            # cut_1和cut_2是索引            cut1 = (left + right) // 2  # 二分的结果            # k = (m+n)*2//2 第k大 cut_1 + cut_2 = k            cut2 = (m + n) - cut1            """            而对于割(Cut),            如果割在‘#’上等于割在2个元素之间,            割在数字上等于把数字划到2个部分,            总是有以下成立:            cutLeft = (cut-1)//2 位置上的元素            cutRight = cut//2 位置上的元素            [#1#2#3#]            """            cut1Left = float('-inf') if cut1 == 0 \                else nums1[(cut1-1)//2]            cut1Right = float('inf') if cut1 == 2 * m \                else nums1[cut1//2]            cut2Left = float('-inf') if cut2 == 0 \                else nums2[(cut2-1)//2]            cut2Right = float('inf') if cut2 == 2 * n \                else nums2[cut2//2]            # 说明数组1的左边元素太大(多),我们把C1减小,相应C2就增多。            if cut1Left > cut2Right:                # c1 左移,c2自动就右移了                right = cut1 - 1            elif cut2Left > cut1Right:                # c1 右移                left = cut1 + 1            else:                break        print("切割的位置:")        print("nums1", nums1, "切割的位置是", cut1)        print("nums2", nums2, "切割的位置是", cut2)        print("cut1Left:",cut1Left)        print("cut2Left:",cut2Left)        print("cut1Right:",cut1Right)        print("cut2Right:",cut2Right)        middle = (max(cut1Left, cut2Left) + min(cut1Right, cut2Right)) / 2.0        print("middle is:", middle)        return middle# leetcode submit region end(Prohibit modification and deletion)if __name__ == '__main__':    s = Solution()    res = s.findMedianSortedArrays3(        [10000],        [10001]    )    print("res:", res)

-----------------------------------------------

如果是第一次阅读文章,可以看看下面的话。

以上内容由平时积累而成,尽量保证代码与注释合在一起,并未做过多篇幅的解释。不一定是最优解,但一定是自己能看得懂的。有疑问的地方还请留言评论。如果题干是原题,就没有写在文章中。后续内容会慢慢发出

欢迎大家评论,收藏和转发。

感谢大家的点赞和关注。

先赞后看,年薪百万

红帽帽,白签签,一起排队做酸酸。愿疫情早日过去。

标签: #数组中位数 leetcode