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寻找两个有序数组的中位数，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

  • Python打印输出数组中全部元素

    学习Python的人都知道数组是最常用的的数据类型,为了保证程序的正确性,需要调试程序. 因此,需要在程序中控制台中打印数组的全部元素,如果数组的容量较小,例如 只含有10个元素,采用print命令或print函数可以答应出数组中的每个元素: 如果数组的容量过大,只能打印出数组的部分元素,打印结果只包含开始部分元素和结尾部分元素,中间元素省略.省略的部分不利于程序的调试: 因此,为了方便调试程序,需要将数组中的元素全部打印出来. 1. 少量元素情况 #打印数组中的元素 import numpy

  • Python实现找出数组中第2大数字的方法示例

    本文实例讲述了Python实现找出数组中第2大数字的方法.分享给大家供大家参考,具体如下: 题目比较简单直接看实现即可,具体的注释在代码中都有: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出数组中第2大的数字 ''' def find_Second_large_num(num_list): ''''' 找出数组中第2大的数字 ''' #直接排序,输出倒数第二个数即可 tmp_list=sorted(num_lis

  • python获取元素在数组中索引号的方法

    本文实例讲述了python获取元素在数组中索引号的方法.分享给大家供大家参考.具体如下: 这里python是通过index方法获取索引号的 li = ['a', 'b', 'new', 'D', 'z', 'example', 'new', 'two', 'elements'] print li.index("example") print li.index("new") print li.index("z") print "c&quo

  • 对python numpy数组中冒号的使用方法详解

    python中冒号实际上有两个意思:1.默认全部选择:2. 指定范围. 下面看例子 定义数组 X=array([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16],[17,18,19,20]]) 输出为5x4二维数组 第一种意思,默认全部选择: 如,X[:,0]就是取矩阵X的所有行的第0列的元素,X[:,1] 就是取所有行的第1列的元素 第二种意思,指定范围,注意这里含左不含右 如,X[:, m:n]即取矩阵X的所有行中的的第m到n-1列数据,含左不含右

  • 详解Python如何获取列表(List)的中位数

    详解Python如何获取列表(List)的中位数

    前言 中位数是一个可将数值集合划分为相等的上下两部分的一个数值.如果列表数据的个数是奇数,则列表中间那个数据就是列表数据的中位数:如果列表数据的个数是偶数,则列表中间那2个数据的算术平均值就是列表数据的中位数.在这个任务里,你将得到一个含有自然数的非空数组(X).你必须把它分成上下两部分,找到中位数. 输入: 一个作为数组的整数(int)列表(list)的. 输出: 数组的中位数(int, float). 示例 get_median([1, 2, 3, 4, 5]) == 3 get_media

  • Python查找两个有序列表中位数的方法【基于归并算法】

    Python查找两个有序列表中位数的方法【基于归并算法】

    本文实例讲述了Python查找两个有序列表中位数的方法.分享给大家供大家参考,具体如下: 今天做到的一个机试题目,很简单,这里简单记录一下: 我用的是归并的思想,当然还可以用递归的方法,下面是具体实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找到两个有序列表的中位数 若列表总长度为奇数则直接返回中间下标的值 否则返回前一个值,如长度为6则返回下标为2处的值 ''' import random def rando

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

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

    Python寻找两个有序数组的中位数 审题: 1.找出意味着这是一个查找算法题 2.算法复杂度log级别,就是提示你是二分查找 3.二分查找实现一般为递归 (1)递归包括递归体  (2)终止条件 思路: 定理: 1.有序数组中有一半的元素小于等于数组的中位数,有一半的元素大于等于中位数(如果数组中元素个数是奇数,那么这里的一半并不是严格意义的1/2) 2.如果我们去掉其中一个数组比中位数小的k个数,再去掉另一个数组中比中位数大的k个数,得到的合并子数组的中位数和原来的中位数相同. eg:[1,2

  • C++实现LeetCode(两个有序数组的中位数)

    [LeetCode] 4. Median of Two Sorted Arrays 两个有序数组的中位数 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and 

  • Python之两种模式的生产者消费者模型详解

    第一种使用queue队列实现: #生产者消费者模型 其实服务器集群就是这个模型 # 这里介绍的是非yield方法实现过程 import threading,time import queue q = queue.Queue(maxsize=10) def Producer(anme): # for i in range(10): # q.put('骨头%s'%i) count = 1 while True: q.put('骨头%s'%count) print('生产了骨头',count) cou

  • Python数据类型之列表和元组的方法实例详解

    引言 我们前面的文章介绍了数字和字符串,比如我计算今天一天的开销花了多少钱我可以用数字来表示,如果是整形用 int ,如果是小数用 float ,如果你想记录某件东西花了多少钱,应该使用 str 字符串型,如果你想记录表示所有开销的物品名称,你应该用什么表示呢? 可能有人会想到我可以用一个较长的字符串表示,把所有开销物品名称写进去,但是问题来了,如果你发现你记录错误了,想删除掉某件物品的名称,那你是不是要在这个长字符串中去查找到,然后删除,这样虽然可行,那是不是比较麻烦呢. 这种情况下,你是不是

  • Python读取文件的四种方式的实例详解

    Python读取文件的四种方式的实例详解

    目录 学生数量特别少的情况 停车场空间不够时怎么办? 怎么加快执行效率? 怎么加快处理速度? 结语 故事背景:最近在处理Wikipedia的数据时发现由于数据量过大,之前的文件读取和数据处理方法几乎不可用,或耗时非常久.今天学校安排统一核酸检查,刚好和文件读取的过程非常相似.正好借此机会和大家一起从头梳理一下几种文件读取方法. 故事设定:现在学校要求对所有同学进行核酸采集,每位同学先在宿舍内等候防护人员(以下简称“大白”)叫号,叫到自己时去停车场排队等候大白对自己进行采集,采集完之后的样本由大白

  • python dict 字典 以及 赋值 引用的一些实例(详解)

    最近在做一个很大的数据库方面的东东,要用到根据数值来查找,于是想到了python中的字典,平时没用过dict这个东东 用的最多的还是 list 和 tuple (网上查 用法一大堆) 看了一下创建字典的方法: 方法1: dict = {'name': 'earth', 'port': 80} 方法2: fdict = dict((['x', 1], ['y', 2])) 方法3: ddict = {}.fromkeys(('x', 'y'), -1) 都实验了一下这些方法,发现不好用,做不出来自

  • python里使用正则的findall函数的实例详解

    python里使用正则的findall函数的实例详解 在前面学习了正则的search()函数,这个函数可以找到一个匹配的字符串返回,但是想找到所有匹配的字符串返回,怎么办呢?其实得使用findall()函数.如下例子: #python 3. 6 #蔡军生 #http://blog.csdn.net/caimouse/article/details/51749579 # import re text = 'abbaaabbbbaaaaa' pattern = 'ab' for match in r

  • JavaScript中十种一步拷贝数组的方法实例详解

    JavaScript中十种一步拷贝数组的方法实例详解

    JavaScript中我们经常会遇到拷贝数组的场景,但是都有哪些方式能够来实现呢,我们不妨来梳理一下. 1.扩展运算符(浅拷贝) 自从ES6出现以来,这已经成为最流行的方法.它是一个很简单的语法,但是当你在使用类似于React和Redux这类库时,你会发现它是非常非常有用的. numbers = [1, 2, 3]; numbersCopy = [...numbers]; 这个方法不能有效的拷贝多维数组.数组/对象值的拷贝是通过引用而不是值复制. // numbersCopy.push(4);

  • 对Python中TKinter模块中的Label组件实例详解

    Python2.7.4 OS-W7x86 1. 简介 Label用于在指定的窗口中显示文本和图像.最终呈现出的Label是由背景和前景叠加构成的内容. Label组件定义函数:Label(master=None, cnf={}, **kw) 其中,kw参数是用来自定义lable组件的键值对. 2. 背景自定义 背景的话,有三部分构成:内容区+填充区+边框 <1>内容区参数有:width,length用于指定区域大小,如果显示前景内容是文本,则以单个字符大小为单位:如果显示的是图像,则以像素为单

  • KnockoutJS数组比较算法实例详解

    这篇文章主要介绍了KnockoutJS数组比较算法实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 前端开发中,数组是一种非常有用的数据结构.这篇博客会解释并分析KnockoutJS实现中使用的数据比较算法. 算法的目的 KnockoutJS使用MVVM的思想,view model中的数组元素会对应data model中的数组数据,当用户进行输入或者请求后台时,数组数据会发生变更, 从而带动UI的更新.例如购物车类的页面,用户可以通过点击

随机推荐