首页 > 代码库 > Median of Two Sorted Arrays

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[]) {
        //嘿嘿
    }
}