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

Example 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

概念：

median：首先需要了解何为median，即我们常说的中位数（针对排序数组来说的），如果为奇数就是正中间的那个数，如果为偶数就是中间的两个数的平均数，like Example 1和Example 2.

思路：

这个题乍看比较容易，但是在LeetCode中给出的Difficulty是hard，关键就在于它对时间复杂度有要求，为O(log (m+n))。对数时间我首先想到的是二分查找，说明该算法的效率一定要与之类似，但又有所限制，确实很难。处理时不能将两个数组合并，不然时间复杂度就提升为线性时间O(m+n)。但我们每次处理需要类似二分查找那样每次平均要处理一半的数。
1.这里我们借用findKthNumber的思想。先实现findKthNumber，如果是偶数个，则把中间2个加起来平均，奇数就用中间的。
2.为了达到对数级的复杂度，我们可以这样：每次在A，B取前k/2个元素。有以下几种情况：
1） A的元素不够k/2，我们可以丢弃B前k/2个元素。反之亦然。
反证法：
假设第K大在B的前k/2中，例如位置在索引m(m<=k/2-1)那么A必然拥有前k中的k -(m+1)个元素，而m<=k/2-1,则m+1<=k/2,k-(m+1)>k/2与条件：A的元素不够k/2矛盾，所以假设不成立，得证。
2）A[mid] < B[mid] (mid是k/2 -1索引处的元素）。这种情况下，我们可以丢弃A前k/2。

1
2
3
4
5
反证法：
假设第K大在A的前k/2中记为maxK，例如位置在索引m(m<= k/2-1)。
那么B必然拥有前k中的k-(m+1)个元素，
而m<=k/2-1,则m+1 <=k/2,k-(m+1)>k/2，推出B[mid]<=maxK。
而A[mid] >= maxK。 推出 A[mid]>=B[mid], 与题设矛盾。

3.知道上面两个结论对我们很重要。接下来，使用D&C来解决一下这个问题。

1
2
3
4
5
6
1.基线条件（有两种情况）：
1）有一个数组为空
2）数组都不为空，k=1（这时候取两个数组最小的元素即可）
2.递归条件：
A[mid] < B[mid]，丢弃A前k/2。（包含两层意思：A或B舍弃k/2;
k做相应变化，k-mid）

源码：

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
def findMedianSortedArrays(num1, num2):
    len_sum = len(num1)+len(num2)
    if(len_sum % 2 == 1):
        return findKth(num1, num2, len_sum/2+1)
    else:
        return (findKth(num1, num2, len_sum/2)+findKth(num1, num2, len_sum/2+1))/2.0

def findKth(A, B, k):
    len1,len2 = len(A),len(B)
    if len(A)==0:
        return B[k-1]
    if len(B)==0:
        return A[k-1]
    if k == 1:
        return min(A[0],B[0])

    mid1 = min(k/2,len1)
    mid2 = min(k/2,len2)

    if A[mid1-1] < B[mid2-1]:
        C = A[mid1:len1]
        return findKth(C,B,k-mid1)
    else:
        C = B[mid2:len2]
        return findKth(A,C,k-mid2)

print findMedianSortedArrays([1,2],[3,4])

备注：不使用D&C，使用循环一样可以实现。这里给出一种使用循环的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def findMedianSortedArrays(nums1, nums2):
        len_sum = len(nums1)+len(nums2)
        if(len_sum % 2 == 1):
            return findKth(nums1, nums2, len_sum/2+1)
        return (findKth(nums1, nums2, len_sum/2)+findKth(nums1, nums2, len_sum/2+1))/2.0

    def findKth(self, A, B, k):
        m,n = len(A), len(B)
        if m > n:
            return findKth(B, A, k)

        left, right = 0, m
        while left < right:
            mid = left + (right-left)/2
            if 0 <= k-1-mid < n and A[mid] >= B[k-1-mid]:
                right = mid
            else:
                left = mid+1
        Ai_minus1 = A[left - 1] if left - 1 >= 0 else float("-inf")
        Bj = B[k - 1 - left] if k - 1 - left >= 0 else float("-inf")
        return max(Ai_minus1,Bj)

注：float(“-inf”)表示负无穷。