Leetcode 编程训练[4]:Median of Two Sorted Arrays

2015-03-30

3 min read

Algorithm , LeetCode , JavaScript

#4：这次的题目比较难：找到两个有序数组A(大小为m)、B(大小为n)的中位数，并且整体时间复杂度为O(log(m+n))。查看提示，这道题与分治法、二分查找有关。

二分查找在计算机科学中，二分查找是在一个有序的数组中寻找目标元素。在每一次查找中，它都会将目标元素与数组中的中间元素进行比较；如果不相等，则取数组的一半再与目标元素进行下一轮查找。这个过程就有分治法的思想：每一次查找步骤就将大问题(一个数组内查找)分解为小问题(这个数组的一半查找)。
别人的分享 MissMary女士提供了一种解法。将数组A、B分割成两部分。将比较小的那一组作为leftPart，比较大的那一组作为rightPart。如果我们能保证leftPart与rightPart的大小相等或相差一相等，并且leftPart所有元素比rightPart的所有元素小，就能很容易找到中位数了。
转换成代码就是：
- 条件一：(i + j == m - i + n - j) || (i + j == m - i + n - j + 1)
- 条件二：A[i] >= B[j - 1] && A[i - 1] <= B[j]
我们在满足条件一的情况下去寻找能满足条件二的结果，通过移动i的位置来寻找结果。如果当前情况下，不满足条件二，就通过二分查找地方式缩小一半的范围。这就需要创建一个标志位，我们将i的范围限定到[iMin, iMax]。当不满足A[i] >= B[j - 1]时，将继续搜索position i的右边（将iMin更新为i+1）;同理，当不满足A[i - 1] <= B[j]时，将继续搜索position i的左边（将iMax更新为i-1）。
整个循环体大概就是这样
```
while(iMin <= iMax){
    //确定本次循环i,j值，满足第一条件
    i = parseInt((iMin + iMax) / 2);
    //m + n + 1保证取余后j不会小于0
    j = parseInt((m + n + 1) / 2) - i;
    //当A[i] < B[j - 1]时，搜索A[]右半边
    if(A[i] < B[j - 1]){
        iMin = i + 1;
    }else if(A[i - 1] > B[j]){
        iMax = i - 1;
    }else{
        //当满足第二条件：，即A[i] >= B[j - 1]、A[i - 1] <= B[j]
		//作下一步处理
    }
```
我们添加一下边界值的情况，不让错误的位置出现。
```
//考虑边界值的情况，使i、j-1有效，A[i] < B[j - 1]时，搜索A[]右半边
if(j > 0 && i < m && A[i] < B[j - 1]){
    iMin = i + 1;
}else if(i > 0 && j < n && A[i - 1] > B[j]){
    iMax = i - 1;
}else{  
```
最后，还需要返回结果。当m+n=奇数时，leftPart比rightPart多一个数，leftPart的右边界就是中位数的位置。并且当i=0时，A[]全体大于B[]，中位数就是B[j-1]；同理当j=0时，中位数就是A[i-1]。在满足条件二的情况下，我们有4个不等式：A[i-1]<=A[i]，B[j-1]<=B[j]，A[i]>=B[j-1]，A[i-1]<=B[j]。得出A[i-1]与B[j-1]中大的那个数就是中位数。我们取个最大值即可Math.max(A[i - 1], B[j - 1])。
当m+n=偶数时，我们需要取中间两个数的平均值。并且当i=m时，A[]全体小于于B[]，中位数就是B[j]；同理当j=n时，中位数就是A[i]。否则为rightPart的左边界值中的最小值Math.min(A[i], B[j])。最后再取个平均就可以了。
```
if(i === 0){
    candLeftPart = B[j - 1];
}else if(j === 0){
    candLeftPart = A[i - 1];
}else{ 
    candLeftPart = Math.max(A[i - 1], B[j - 1]);
}
//整体大小为奇数
if((m + n) % 2 == 1){
	return candLeftPart;
}  
//整体大小为偶数
if(i == m){
    candRightPart = B[j];
}else if(j == n){
    candRightPart = A[i];
}else{
    candRightPart = Math.min(A[i], B[j]);
}
return (candLeftPart + candRightPart) / 2;
```
这种方案只用到了二分查找，对于分治还没有利用，不过时间复杂度O(log(min(m,n)))。有种使用O(log(m+n))的解法与合并排序的流程有点类似。每调用一次划分函数，查询规模都减少一半。就是本方法的迭代方法。

源码

Leetcode 编程训练[4]:Median of Two Sorted Arrays

See Also