446e96edcab7efca7267db258655bf4f
Problem 4: Median of Two Sorted Arrays

Problem 4: Median of Two Sorted Arrays

链接:https://leetcode.com/problems/median-of-two-sorted-arrays/

难度等级:Hard(困难)

题干

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

You may assume nums1 and nums2 cannot be both empty.

题意

给定两个有序数组,返回两个数组所有元素当中的中位数

样例

Example 1:

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

The median is 2.0
Example 2:

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

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

分析

这是我们碰到的第一道hard问题,我曾经就在面试的过程当中被问过原题。当时想了好久才想到思路,然而虽说想到了思路,但是真正用代码实现还是比较麻烦的。

两个有序数组求中位数,很容易想到可以把两个数组的元素合并在一起然后排序,返回中间位置的元素。

这样当然是可行的,然而由于用到了排序,整体是O(NlogN)的复杂度,所以耗时会很大,而且完全忽略了数组的有序性。

那怎么能利用数组的有序性呢?

比较容易想到归并排序的思路,把两个数组归并,然后找到中位数即可。这种方法的复杂度是O(N),想必NlogN有了很大的提高,但仍然不是最优的。

说到有序性,几乎必然会想起的一个算法就是二分。这一点在面试当中尤为明显,当面试官提到某某数组,某某矩阵是有序的时候,第一反应就应该是二分。

但在这里,我们涉及到的不是一个数组,而是两个,该怎么二分呢?

还记得我们的Problem 1吗?我们要在数组当中发觉a b两个数,使得它们的和等于target。我们是怎么做的优化?我们枚举了所有的a之后,还有必要枚举所有的b吗?

同理,在这里也是一样的思路。

也许你还看不明白,没关系,我们把题目的意思做一个简单的变形,你一定就会懂了。我们要找两个数组的中位数,其实就等于在两个数组合并在一起的元素集合当中找到中间大小的数。所谓的中间大小,也就是排名为(len(a) + len(b)) / 2的数。而一个数在两个集合当中的排名,其实可以转化成两个集合的排名相加。

打个比方说,35在a数组中排名10,在b数组中排名20,那么在全体数据当中它排名多少呢?显然,它应该排29位。

因为a和b两个数组都是有序的,所以35在a中的排名就等于它的下标,在b中的排名呢?我们不知道,但是可以通过二分法快速求到。

所以你是不是会告诉我,可以通过两次二分的方法求解呢?

最外层的二分法用在a数组当中寻找元素,其中一层二分法用来计算该元素在b数组当中的排名,整个算法的复杂度,估计你也会迅速地告诉我:O(logNlogN)

改进

但仔细想想看,第二层二分法真的有必要么?

我们已经知道了某个数在a数组当中排名为x,我们想要知道它在b数组的排序y是不是满足要求,使得x+y=traget。

我们当然可以把y计算出来之后再判断是否满足要求,但是,我们不能直接判断target-x是否有解吗?

在有序的数组(升序)当中,如果我们想知道某个数x,是否是数组里最大的数应该怎么办?当然是和数组的最后一个元素比较了,那如果想知道是否是第二大呢?当然要比现在的第二大要大,比第一大要小了。

同理,我们想知道x是否能在b数组排在k位置呢?

显然应该满足如下要求:

b[k-1]<=x<=b[k]

如果x > b[k]呢?说明我们的x取太大了,两个数组里加起来的排序太大,我们应该取小一点。

如果x < b[k-1]呢?说明x取太小了,应该取大一点。

写成伪代码:

top Created with Sketch.