Median of Two Sorted Arrays

①原题

There are two sorted arrays A and B 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)).

②乡村英语翻译一下

给你两个排序数组，容量为m的数组A，容量为n的数组B。求出两个数组的中位数（啥玩意？），硬性要求时间复杂度O(log (m+n)).

③读题

1：太汗颜了，median到底是个啥，查一下：

中位数是在一组数据中居于中间的数(特别注意的地方是：这组数据之前已经经过升序排列！！！)，即在这组数据中，有一半的数据比它大，有一半的数据比它小。如果这组数据包含偶数个数字，中值是位于中间的两个数的平均值。

2：好吧，中位数是这么个玩意，那么理论上首先我们需要先将两个数组合为一，再求这个新合并的数组的中位数。

3：但是，已经限定死了时间复杂度为log（m+n），原来LeetCode的题目也思路不开放嘛。

4：问题可以转化成两个有序序列找第num大的数，用类似二分的思想，用递归处理。

④解题

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        //嘿嘿
    }
}

Median of Two Sorted Arrays,布布扣,bubuko.com

Median of Two Sorted Arrays

原文：http://my.oschina.net/u/1994258/blog/303757