Python寻找两个有序数组的中位数实例详解

yipeiwu_com6年前Python基础

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

审题:

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

2.算法复杂度log级别,就是提示你是二分查找

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

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

思路:

定理:

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

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

eg:[1,2,3],[1,2,3] => [1,1,2,2,3,3]

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

解题思路:

假设两个数组的中位数分别是a[m1],b[m2]

1.if a[m1] == b[m2] ,那么刚好有一半的元素小于a[m1],那么a[m1]就是要找的中位数。参考上面的列子

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

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

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

结论就是:只能删除a的n1/2(向下取整)

3.if a[m1] > b[m2],和上面分析类似,中位数只能出现在a的前半段或者b的后半段。也就是说a[0 ~ n1/2]和b[n1/2 ~ n2-1]的中位数和原来的中位数相同。

参考:LeetCode参考答案

class Solution:
  def findMedianSortedArrays(self, nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: float
    """
    m, n = len(nums1), len(nums2)
    if m > n:
      nums1, nums2, m, n = nums2, nums1, n, m
    if n == 0:
      raise ValueError
    imin, imax, half_len = 0, m, (m + n + 1) // 2
    while imin <= imax:
      i = (imin + imax) // 2
      j = half_len - i
      if i < m and nums2[j-1] > nums1[i]:
        # i is too small, must increase it
        imin = i + 1
      elif i > 0 and nums1[i-1] > nums2[j]:
        # i is too big, must decrease it
        imax = i - 1
      else:
        # i is perfect
        if i == 0: max_of_left = nums2[j-1]
        elif j == 0: max_of_left = nums1[i-1]
        else: max_of_left = max(nums1[i-1], nums2[j-1])
        if (m + n) % 2 == 1:
          return max_of_left
        if i == m: min_of_right = nums2[j]
        elif j == n: min_of_right = nums1[i]
        else: min_of_right = min(nums1[i], nums2[j])
        return (max_of_left + min_of_right) / 2.0

总结

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

相关文章

详解Django中间件的5种自定义方法

详解Django中间件的5种自定义方法

Django中间件 在http请求 到达视图函数之前 和视图函数return之后,django会根据自己的规则在合适的时机执行中间件中相应的方法。 中间件的执行流程 1、执行完所有的re...

Python字典的核心底层原理讲解

Python字典的核心底层原理讲解

字典对象的核心是散列表。散列表是一个稀疏数组(总是有空白元素的数组),数组的每个单元叫做 bucket。每个 bucket 有两部分:一个是键对象的引用,一个是值对象的引用。所有 buc...

python 参数列表中的self 显式不等于冗余

self在区分全局变量/函数和对象中的成员变量/函数十分有用。例如,它提供了一种作用域机制,我个人认为比Ruby的@和@@清晰多了,这可能是习惯使然吧,但它确实和C++、Java中的th...

OpenCV 轮廓检测的实现方法

OpenCV 轮廓检测的实现方法

轮廓概述 轮廓可以简单认为成将连续的点(连着边界)连在一起的曲线,具有相同的颜色或者灰度。轮廓在形状分析和物体的检测和识别中很有用。  为了更加准确,要使用二值化图像...

python基于K-means聚类算法的图像分割

python基于K-means聚类算法的图像分割

1 K-means算法 实际上,无论是从算法思想,还是具体实现上,K-means算法是一种很简单的算法。它属于无监督分类,通过按照一定的方式度量样本之间的相似度,通过迭代更新聚类中心,...