求两个有序数组的中位数

算法

题目

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)).

很容易想到是用分治来做，但是我自己在写代码的时候，讨论奇偶和最后终止时的边界实在是太烦了，写出来我自己都看不下去，肯定有更简单的办法。于是翻了翻大神们的答案，有下面这样一个解法。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def findMedianSortedArrays(self, A, B):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        l = len(A) + len(B)
        if l % 2 == 1:
            return self.findKth(A, B, l//2)
        else:
            return (self.findKth(A, B, l//2-1) + self.findKth(A, B, l//2))/2.0


    def findKth(self, A, B, k):
        if len(A) > len(B):
            A, B = B, A
        if not A:
            return B[k]
        if k == len(A) + len(B) - 1:
            return max(A[-1], B[-1])
        i = len(A)//2
        j = k-i
        if A[i] > B[j]:
            return self.findKth(A[:i], B[j:], i)
        else:
            return self.findKth(A[i:], B[:j], j)

不愧是大神，我怎么就没想到用findKth来简化奇偶性的讨论呢。但是这个findKth我又奇怪了，j = k - i 的时候，难道不怕数组越界？还真是不怕，注意到k的初始取值是总长度的一半，它总能让i和j在边界条件终止并退出递归。

然后这个递归条件的思路是这样的：

从运行时间上来说，每次递归丢掉了k个数，而k至少比A，B中较短的那个数组长度的一半要大，所以可以达到O(log(m+n))。