前言:
目前各位老铁们对“数组中位数 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