1 题目描述

给定两个排好序的数组，找出这两个数组并集的中位数。
示例：

input : A = [1,3,5,7] ; B = [2,4,6,8,10]
out : 5

2 题目分析

看到这道题最直接的想法就是，先把两个数组合并到一起，然后寻找中位数。
这种方法显然时间复杂度比较高，一种更有效的思路是二分法。

2.1 A 和 B 的并集中第 k 小的数。

首先我们考虑A 和 B 的并集中第 k 小的数。
假设 A 和 B 的元素个数都大于 k//2，我们将A的第 k//2 个元素（即A[k//2 - 1]）和 B 的第 k - k//2 个元素（即B[(k - k//2) -1]）进行比较，有以下三种情况（为了简化这里先设 k 是偶数，k 是奇数同样成立）。
1. A[k//2 - 1] < B[k - k//2 -1]。
为了具体看，假设 k = 7，则k//2 = 3, k - k//2 = 4。所以观察 A[2] = 5和 B[3] = 8，A[2] < B[3]，因为A是从小到大排好序的，所以A[0], A[1], A[2] 都小于B[3]，意味着 A[0]到A[2] 的肯定在A和B的所有元素的前k个元素的范围内。所以问题可以转化为寻找A[3:] 和 B 中第4小的数，即“在 A 和 B 中寻找第 k 小的数”转化为“在 A[k//2 : ] 和 B 中寻找第 k-k//2 个数”。
2. A[k//2 - 1] > B[k - k//2 -1]。
同理，问题转化为“在 A 和 B[(k - k//2) :] 中寻找第 k//2 个数”。
3. A[k//2 - 1] = B[k - k//2 -1]。
归到上面任一种情况都可以。

注：上面我们假设了A 和 B 的元素个数都大于 k//2，为了兼顾各种情况，用
pa = min(k//2, len(A))来表示索引值，pb = k - pa。

2.2 A 和 B 的中位数

如果 A 和 B 加起来个数是奇数，则寻找第 (len(A) + len(B))//2 + 1个数。
如果 A 和 B 加起来个数是偶数，则返回第(lenA+lenB)//2个数和(lenA+lenB)//2 + 1个数的平均值。

3 代码

class Solution:
    def getKth(self, A, B, k):
        '''
        type A : list
        type B : list
        type k : int
        rtype : 
        '''
        lenA = len(A); lenB = len(B)
        if lenB < lenA: return self.getKth(B, A, k)
        if lenA == 0: return B[k-1]
        if k == 1: return min(A[0], B[0])
        pa = min(k // 2, lenA); pb = k - pa
        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 A : list
        type B : list
        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

A = [1,3,5,7]
B = [2,4,6,8,10]            
s = Solution()
s.findMedianSortedArrays(A, B)