leetcode 4 — Median of Two Sorted Arrays

之前做过一道类似的题目,是卜老师算法课作业中的一题,那个题目与此题唯一的不同之处在于此题的两个数组的长度不同。在之前的问题,由于长度相同,每次都可以很好的找到数组的切分点(直接选取两个数组中间的数)。但对于长度不等的两个数组,找到合适的切分点成了关键的问题。

因为要找的是中位数,所以最后的切分一定满足

partitionA+partitionB = (lengthA + lengthB + 1) / 2。

partition是划分位置,也代表左边的数字个数。

分子的+1保证的是左边的数字个数多于右边数字的个数(不加一的话是右边比左边多一个)。由于这个条件,在确定partitionA的情况下,计算partitionB,为保证partitionB不为负,A的长度需要小于B的长度。

既然已经有了一个条件需要满足,那么只要确定partitionA的值,partitionB也随之确定。所以对partitionA的赋值为:

partitionA = (Astart + Aend) / 2

Amin和Amax是两个下标,用于查找对于A的合适划分位置。

Astart的初始值为0,Aend为lengthA。计算出A,B的划分位置之后,开始判断划分位置是否满足条件,并作出适应的调整。

因为第一个条件的控制,左右两边的数字个数是没有问题的,偶数长度情况下两边相等,奇数长度情况下左边多一个数字。

另一个需要判断的条件是大小的判断。左侧的最大值需要小于右侧的最小值,因为数字是分在两个数组中,对于同一个数组,因为是排好序的,所以左侧一定小于右侧。所以判断任务明确了:

max_left(A) < min_right(B)

max_left(B) < min_right(A)

如果第一个条件不满足,则说明A的左侧有不满足条件的数字,需要减小partitionA,将分割线左移。所以令Aend = partitionA – 1。然后更新partitionA继续判断。

如果是第二个条件不满足,则说明A的右侧有不满足条件的数字,需要增大partitionA,将分割线右移。令Astart = partitionA + 1。 然后更新partitionA继续判断。

两个条件都满足的时候就代表A,B的划分是正确的,然后只需要找中位数了。

如果两个数组长度之和为偶数,那么返回左边最大值和右边最小值的平均数即可。

如果两个数组长度之和为奇数,那么返回左边的最大值即可。

在实现的过程当中,需要考虑数组边界的问题。因为两个数组的长度不一样,可能会有partitionA为0或lengthA的情况,也可能是partitionB为0或lengthB的情况。如果不考虑的话,会出现数组越界问题。

Leave a Reply

Your email address will not be published. Required fields are marked *