[Leetcode][python]Median of Two Sorted Arrays/两个排序数组的中位数

梦里梦外; 2022-06-09 06:49 140阅读 0赞

## 题目大意 ##

求两个已经排好序的数列的中位数

## 解题思路 ##

下面两个方法也适用于查找第k大的数

### 方法一 ###

[https://www.cnblogs.com/TenosDoIt/p/3554479.html][https_www.cnblogs.com_TenosDoIt_p_3554479.html]

复杂度为O（k）的算法，在归并两个数组的过程中，如果如果已经选择的元素达到k（或中位数），就不需要再归并下去了。

### 方法二 ###

转自：[http://www.cnblogs.com/zuoyuan/p/3759682.html][http_www.cnblogs.com_zuoyuan_p_3759682.html]

首先我们来看如何找到**两个数列的第k小个数**，即程序中getKth(A, B , k)函数的实现。

用一个例子来说明这个问题：

A = \{1，3，5，7\}  
B = \{2，4，6，8，9，10\}；

如果要求第7个小的数，A数列的元素个数为4，B数列的元素个数为6；

k/2 = 7/2 = 3，而A中的第3个数A\[2\]=5；B中的第3个数B\[2\]=6；

A\[2\]小于B\[2\]；则A\[0\]，A\[1\]，A\[2\]中必然不可能有第7个小的数。

因为A\[2\]小于B\[2\]，所以比A\[2\]小的数最多可能为A\[0\], A\[1\], B\[0\], B\[1\]这四个数，也就是说A\[2\]最多可能是第5个大的数，由于我们要求的是getKth(A, B, 7)；现在就变成了求getKth(A’, B, 4)；

即A’ = \{7\}，因为A\[0\]，A\[1\]，A\[2\]中没有解，所以我们直接删掉它们就可以了。

B不变，求这两个数列的第4个小的数，这个可以使用递归来实现。

## 代码 ##

class Solution(object):
    
        def getKth(self, A, B, k):
            lenA = len(A)
            lenB = len(B)
            if lenA > lenB:  # 保证A比B短
                return self.getKth(B, A, k)
            if lenA == 0:  # A已为空，直接返回B中间数
                return B[k - 1]
            if k == 1:   # 如果找的是第一个，直接返回两个数组比较小的那个
                return min(A[0], B[0])
    
            pa = min(k/2, lenA)
            print 'pa:', pa, 'pb', k-pa
            pb = k - pa
    
            print 'A[pa - 1]', A[pa - 1], 'B[pb - 1]',B[pb - 1]
            # 索引为pa和pb，所以是A[pa - 1] 和 B[pb - 1]
            if A[pa - 1] <= B[pb - 1]:
                return self.getKth(A[pa:], B, pb)
            else:
                return self.getKth(A, B[pb:], pa)
    
        def findMedianSortedArrays(self, A, B):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: float
            """
            lenA = len(A)
            lenB = len(B)
            if (lenA + lenB) % 2 == 1: 
                return self.getKth(A, B, (lenA + lenB)/2 + 1)
            else:
                return  (self.getKth(A, B, (lenA + lenB)/2) + self.getKth(A, B, (lenA + lenB)/2 + 1)) * 0.5

## 总结 ##

分治法

[https_www.cnblogs.com_TenosDoIt_p_3554479.html]: https://www.cnblogs.com/TenosDoIt/p/3554479.html
[http_www.cnblogs.com_zuoyuan_p_3759682.html]: http://www.cnblogs.com/zuoyuan/p/3759682.html