Python寻找两个有序数组的中位数实例详解 - 行业资讯 - 肥雀云

Python寻找两个有序数组的中位数

<>强审题:

1。找出意味着这是一个查找算法题

2。算法复杂度日志级别,就是提示你是二分查找

3。二分查找实现一般为递归

,(1)递归包括递归体
　　,(2)终止条件

<>强思路:

<强>定理:

1。有序数组中有一半的元素小于等于数组的中位数,有一半的元素大于等于中位数(如果数组中元素个数是奇数,那么这里的一半并不是严格意义的1/2)
　　

2。如果我们去掉其中一个数组比中位数小的k个数,再去掉另一个数组中比中位数大的k个数,得到的合并子数组的中位数和原来的中位数相同。
　　

<代码>如:[1,2,3],[1,2,3]=比;(1、1、2、2、3、3]
　　

根据定理去除元素[2、3],[1,2]=比;(1、2、2、3)中位数没变。我用了特殊的例子解释,你可以自行换一个试一试。如果两个的数组长度不一样的时候,不能去掉各自的一半,要去掉相同的个数、下面会细说

<>强解题思路:

假设两个数组的中位数分别是(m1), b (m2)
　　

1。如果一个(m1)==b (m2),那么刚好有一半的元素小于(m1),那么一个(m1)就是要找的中位数。参考上面的列子
　　

2。如果一个(m1) & lt;b (m2),根据定理1可知,这个中位数只可能出现在一个[n ~ n1-1]或者b [0 ~ n2/2]。也就是说合并这两个数组的中位数和原来的数组合并的数组的中位数是一样的,根据定理2可知:
　　

1。数组长度一样的时候,去除掉一半是合理的。
　　

2。数组长度不一样,这么做中位数可能发生变化。解决方案就是去除掉相同个数的元素,为什么?假设n1 & lt;n2,两个数组就去掉n个元素。那就不在是上面的范围([n ~ n1-1]或者b [0 ~ n2/2]),而是一个[n ~ n1-1]或者b [0 ~ (n + n2-1)]。
　　

结论就是:只能删除一个的n(向下取整)

3。如果一个(m1)的在b (m2),和上面分析类似,中位数只能出现在一个的前半段或者b的后半段。也就是说a [0 ~ n]和[n ~ n2-1]的中位数和原来的中位数相同。

参考:LeetCode参考答案

　　　　　　类解决方案: 　　def findMedianSortedArrays(自我、nums1 nums2): 　　”“” 　　:类型nums1:列表(int) 　　:类型nums2:列表(int) 　　:rtype:浮动　　”“” 　　m, n=len (nums1), len (nums2) 　　如果m比;护士: 　　nums1 nums2, m, n=nums2, nums1, n, m 　　如果n==0: 　　提高ValueError 　　imax, imin half_len=0, m, (m + n + 1)//2 　　而imin & lt;=imax: 　　我=(imin + imax)//2 　　j=half_len——我　　如果我& lt;m和nums2 [j - 1]比;nums1[我]: 　　#我太小,必须增加　　imin=i + 1 　　elif我比;0和nums1祝辞(张)nums2 [j]: 　　#我太大,必须减少它　　imax=i - 1 　　其他: 　　#我是完美的　　如果我==0:max_of_left=nums2 (j - 1) 　　elif j==0: max_of_left=nums1(张) 　　其他:max_of_left=max (nums1(张),nums2 [j - 1]) 　　如果(m + n) % 2==1: 　　返回max_of_left 　　如果我==m: min_of_right=nums2 [j] 　　elif j==n: min_of_right=nums1[我] 　　其他:min_of_right=min (nums1[我],nums2 [j]) 　　返回(max_of_left + min_of_right)/2.0 　　　　

以上所述是小编给大家介绍的Python寻找两个有序数组的中位数,希望对大家有所帮助,如果大家有任何疑问请给我留的言,小编会及时回复大家的。在此也非常感谢大家对网站的支持!