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

作者 : 开心源码 本文共1506个字,预计阅读时间需要4分钟 发布时间: 2022-05-12 共141人阅读

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

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Python寻觅两个有序数组的中位数

发表回复