Median of Two Sorted Arrays

两个已经排好序的数组,求中间的数值。要求时间复杂度是:O(log (m+n))

比如:

A:1、2

B:1、3

1、1、2、4 的中间值是:(1+2)/2==1.5

 

A:1、2、3

B:1、3

1、1、2、3、3 的中间值是:2

看到题目要求是O(log (m+n))就知道是要用二分法去查找我们需要的那个数

 

1、如果不考虑时间复杂度

m=A.length  ;  n= B.length;

mid = (m + n -1) /2

然后再for循环遍历A数组和B数组,很快就能找到mid,再考虑奇偶数目的情况。时间复杂度在o((m+n-1)/2)

 

2、考虑时间复杂度为O(log (m+n))的情况

思考1:因为两个数组都是排好序的,所以用二分查找法并比较。

首先找到第 mid = (m + n -1) /2 个大的数字,可能出现在A中,也可能出现在B中,所以在A和B中搜索。

count=0是计数器。i=j=0;先比较A[i]与B[j],如果A[i]更小,那么判断A[i+(A.length-i)/2]这个是否也更小,如果更小则赋值给i(相当于i移动),然后再循环判断,如果A[i]更大,那么判断B[j+(B.length-j)/2] 与A[i],每次i,j移动的时候都要给count增加,如果count==mid,那么最后找到第mid个数字。

找到第mid个数字之后,再判断下一个大的数字,计算median值。

实现起来发现思路不清晰,实现复杂。

 

思考2:

假设A数组元素更少,B数组元素更多。
(如果A更多,B更少,那么交换A与B,保证A数组元素更少。)

因为首先要找到第mid个大的数字,所以它可能在A中,也可能在B中,可以确定的是,如果是A中第M  (即A[M-1]) 个数字是所求,那么B中小于A中第M个数的应该是第mid – M (即B[mid-M-1])。

程序运行时:如果A[i]<=B[j],那么所求数字在i的右侧,i继续向右,如果A[i]>B[j],那么所求数字在i的左侧,右边界缩减。

最终确定所求的第mid数字

再根据奇偶性判断下一个数字,最终求得median

下面是代码:

public class Median {
    public double findMedianSortedArrays(int A[], int B[]) {
        int n = A.length;
        int m = B.length;
        // the following call is to make sure len(A) <= len(B).
        // yes, it calls itself, but at most once, shouldn't be
        // consider a recursive solution
        if (n > m)
            return findMedianSortedArrays(B, A);

        // now, do binary search先找第一个数(偶数个数字需要找两个,奇数个数字需要找一个)
        int k = (n + m - 1) / 2;//k是median,n+m=100,k是49即第50个数字(再找第51个);101个数,k是50即第51个数字
        int l = 0, r = Math.min(k, n); // r is n, NOT n-1, this is important!!
        //r选择为k和n中的最小,因为要找的中间的数字可能在A数组中,也有可能在B中。k小于n,在A中,k大于n,在B中
        //k等于n,r=k=n
        while (l < r) {//0到r-1 开始循环,l是左边界,r是右边界
            int midA = (l + r) / 2;//从0开始二分法找midA
            int midB = k - midA;//midB是要找的第k个-midA,midA+midB==k,A数组前midA个数+B数组前midB个数
            if (A[midA] < B[midB])//如果A[midA]<B[midB],说明要找的第K个数不再A数组midA之前
                l = midA + 1;       //L重新开始二分查找,L = midA+1
            else                    //如果A[midA]>=B[midB],说明要找的第K个数在A中,缩小范围
                r = midA;       //r=midA,缩小右边界范围
        }
        //跳出循环的时候 l == r
        // after binary search, we almost get the median because it must be between
        // these 4 numbers: A[l-1],  B[k-l+1],  A[l], B[k-l], 

        //以下两种情况
        // if (n+m) is odd, the median is the larger one between A[l-1] and B[k-l].
        // and there are some corner cases we need to take care of.
        int a = Math.max(l > 0 ? A[l - 1] : Integer.MIN_VALUE, k - l >= 0 ? B[k - l] : Integer.MIN_VALUE);
        if (((n + m) & 1) == 1)//判断是奇数
            return (double) a;

        // if (n+m) is even, the median can be calculated by
        //      median = (max(A[l-1], B[k-l]) + min(A[l], B[k-l+1]) / 2.0
        // also, there are some corner cases to take care of.
        int b = Math.min(l < n ? A[l] : Integer.MAX_VALUE, k - l + 1 < m ? B[k - l + 1] : Integer.MAX_VALUE);
        return (a + b) / 2.0;
 }



 

 

 

Tagged on: ,

2 thoughts on “Median of Two Sorted Arrays

  1. mayanist

    你好,能详细解释一下为什么退出二分的while循环之后,结果会再那4个数之间吗?特别是A[l-1]这个,该怎么理解

    1. crsbrk Post author

      int L = 0, R = Math.min(k, n);
      左边界是0;右边界是 是n;(前提保证A长度< = B的长度,R都会等于n) 每次循环的时候 while (l < r) { int midA = (l + r) / 2; int midB = k - midA; if (A[midA] < B[midB]) l = midA + 1; else r = midA; } 试想如果K在B中,那么循环到最后 L ==R==N, 而N是A数组的长度,所以A中最大的应该是A[L - 1],相对应的B[ K- (L-1) ] 如果K在A中,那么循环到最后 L ==R < N, 所求的是A[L - 1],相对应的B[ K- (L-1) ] A[ L - 1 ] 下一个是A[ L ],相对应的是B[K - L] 还会出现特殊情况,比如A是空,或者B是空,所以需要如下类似的判断 int a = Math.max(l > 0 ? A[l – 1] : Integer.MIN_VALUE, k – l >= 0 ? B[k – l] : Integer.MIN_VALUE);

      int b = Math.min(l < n ? A[l] : Integer.MAX_VALUE, k - l + 1 < m ? B[k - l + 1] : Integer.MAX_VALUE); 最好debug程序一步一步看下,这儿有一个函数的解释https://leetcode.com/discuss/11174/share-my-iterative-solution-with-o-log-min-n-m

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.