Median of Two Sorted Arrays, Leetcode 解题笔记

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

这道题乍一看感觉很简单,合并两个数组找到中位数即可,复杂度是O(m+n),但是题目要求的时间复杂度限制了这种方法,导致这道题的难度直接达到了leetcode的最高难度5。 所以如果你没能解出这道题,也不用过于沮丧,其实大家都一样!其实,即使我从网上看完答案,也只是理解了其思路,具体实现的过程中还有很多小技巧,并不是短时间可以想到的。相信在实际面试中遇到这道题的几率不会很高,如果真的遇到了,只能说运气不好。言归正传,下面来看一下最优解法。

面对中位数问题,肯定首先要考虑数组长度的奇偶问题,这里要分两种情况,很简单,不再多说。

另外看到要求的复杂度是O(log(m+n)), 应该立刻反应到binary search的方法。那么这道题如何利用binary search的思路求解呢,其实可以把题目转化为:找一个unioned sorted array中的第k大(从1开始数)的数, 又等价于寻找并判断两个sorted array中第k/2(从1开始数)大的数。

那么如何判断两个有序数组A,B中第k大的数呢?我们需要判断A[k/2-1]和B[k/2-1]的大小。

如果A[k/2-1]==B[k/2-1],那么这个数就是两个数组中第k大的数。

如果A[k/2-1]<B[k/2-1], 那么说明A[0]到A[k/2-1]都不可能是第k大的数,所以需要舍弃这一半,继续从A[k/2]到A[A.length-1]继续找。当然,因为这里舍弃了A[0]到A[k/2-1]这k/2个数,那么第k大也就变成了,第k-k/2个大的数了。

如果 A[k/2-1]>B[k/2-1],就做之前对称的操作就好。这样整个问题就迎刃而解了。

当然,边界条件页不能少,需要判断是否有一个数组长度为0,以及k==1时候的情况。

因为除法是向下取整,并且页为了方便起见,对每个数组的分半操作采取:

int a = Math.min(k/2,m);
int b = k – b;

为了能保证上面的分半操作正确,需要保证A数组的长度小于B数组的长度。

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int m = A.length;
        int n = B.length;
        int total = m + n;
        if(total % 2 == 0){
            return (getMedian(A, 0, m-1, B, 0, n-1, total/2) + getMedian(A, 0, m-1, B, 0, n-1, total/2+1))/2;
        }
        else{
            return getMedian(A, 0, m-1, B, 0, n-1, total/2+1);
        }
        
    }
    
    public static double getMedian(int[] A, int astart, int aend, int[] B, int bstart, int bend, int k){
        int m = aend - astart + 1;
        int n = bend - bstart + 1;
        
        if(m &gt; n){
            return getMedian(B, bstart, bend, A, astart, aend, k);
        }
        if(m == 0){
            return B[k-1];
        }
        if(k == 1){
            return Math.min(A[astart], B[bstart]);
        }
        
        int a = Math.min(k/2, m);
        int b = k - a;
        if(A[astart + a - 1] &lt; B[bstart + b -1]){
            return getMedian(A, astart + a, aend, B, bstart, bend, k-a);
        }
        else if(A[astart + a - 1] &gt; B[bstart + b -1]){
            return getMedian(A, astart, aend, B, bstart + b, bend, k-b);
        }
        else{
            return A[astart + a -1];
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s