leetcode: Median of Two Sorted Arrays

问题描述：

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

 

原问题链接：https://leetcode.com/problems/median-of-two-sorted-arrays/

 

问题分析

median的定义

    这个问题相对来说比较复杂。我们需要针对问题来一步步详细的分析。首先来理解一下median的定义。给定两个已经排序的数组，求它们的中位数。对于这个中位数，我们的理解可能会存在一定的偏差。一般来说会把这个数字当成一个数组中间的那个元素。比如说[1, 2, 3, 4, 5]，对于它来说，中位数是3。可是对于有偶数个元素的数组呢？它的n/2和n/2 + 1是最中间的两个元素。

    实际上，中位数指的是如下的关系：

median = a[n/2 + 1] (如果n为奇数)

median = (a[n/2] + a[n/2 + 1]) /2 (如果n为偶数) 

    对于奇数个元素来说，它最中间的那个元素确实是使得它两边的元素一样多。而对于偶数个的元素来说，它最中间的是两个元素，所以要取这两个元素的平均值。举例来说，假设我们有两个数组[1, 2, 3] [5, 6, 7]，那么它们的中间值则为(3 + 5) / 2 = 4。如果我们有数组[1, 2]和[3, 4, 5]因为总元素的个数为奇数，它的中间值则为3。

    因为这个问题本身是针对两个不一定长度一致的数组，假设两个数组a[], b[]它们的长度分别为m, n。那么根据前面的讨论，就需要根据m + n的值来确定。如果m + n为奇数，假设两个数组合并成一个排序的数组。那么最后要取得的数字是位于(m + n) / 2这个位置的元素。而如果m + n为偶数，最后要取的数字是位于(m + n) / 2 - 1和(m + n) / 2这两个位置元素的平均值。

    现在，对于median的位置和定义已经清楚了。在两个排序的数组中该如何去寻找这个值呢？

 

第k个元素的推导

    对于求中值的问题，其更加一般化的问题可以归结为求第k个元素的问题。 我们这里的中间值正好是求第k个值的一种特例。

     现在，我们就从一个一般的情况来分析取第k个元素的场景。假设我们要取第k个元素的时候，在数组a中间选择的元素点是i，这个i表示的是a中间的第i个，不是索引i。那么，对应的在另外一个数组b中间对应位置的k-i个是我们需要比较的对象。它们的关系如下图：

    如果这个时候位置为i的元素，也就是数组a里a[i - 1]的元素等于对应比较的元素，即b[k - i - 1]的元素，这表示包含这两个元素在内以及它们之前的数组a,b中的所有元素正好有k个。我们取a[i-1]或者b[k-i-1]作为找到的目标结果值。当然这个时候a[i-1] == b[k-i-1]。

    如果这个时候，a[i-1]和b[k-i-1]不相等的话，那么就需要根据它们的比较来确定下一步的比较搜索范围。我们该怎么来调整这个搜索范围呢？针对这两种情况来讨论，假如a[i - 1] > b[k - i]，这个时候表示a串中第i个元素它在对应的数组b中排到比期望的还要靠后才满足a[i-1] < b[m], m > k - i。所以这个时候我们要找的元素肯定在a[i - 1]的左边范围内。因为在a[i-1]右边的只会更大。这种情况如下：

    对于另外一种情况，就是如果a[i-1] < b[k - i - 1]，那么表示a[i-1]这个元素所大于的元素还不到k个，这个时候需要去看a[i-1]后面的元素，如下图：

     上述的讨论算是确定了一个基本的思路。笼统的来说，当a[i - 1] > b[k - i - 1]时，我们应该到下一个范围内去查找。这个范围对于数组a来说，它是在a[l]到a[i-1]这个范围内。这里l表示数组a最左边的索引。最开始l = 0。而对于数组b来说，它的缩小的范围是在b[k - i - 1]到b[r]之间。最开始r = n - 1。假设n是数组b的长度。

    当a[i - 1] < b[k - i - 1]时，可以得到类似的推论，对于数组a来说，它的范围则是a[i - 1]到a[r]，r是数组a最右边的索引。对于数组b来说，它的范围则是b[l]到b[k - i - 1]。这样，我们就概括出来了这么一个大致的过程。再往下进一步的细化。我们该怎么来描述这个逐步缩小搜索范围的过程呢？最开始查找的时候定义的这个长度范围k是多少比较合适呢？还要一个就是程序的退出条件是什么呢？这些我们进一步来讨论。

    首先来看怎么定义k和搜索长度。这个相对比较简单，可以直接借鉴二分查找的方法。假设要查找在两个数组里排第k个的元素，这种二分查找的思路就是首先取k / 2，然后拿数组a里a[k / 2] 这个数字去比较在数组b里对应的数字。假设也是b[k/2]。如果a[k / 2] = b[k / 2]，这就是正好我们要找的元素了。当然，这里还有一个值得考虑的细节，那就是因为数组a, b长度不一定相等，我们不能拿k / 2这个索引直接到数组a里面直接套，如果k / 2比数组a的长度还要大，那该怎么办呢？这是一个容易疏忽的地方。所以这里一种比较合理的办法就是取Math.min(k / 2, ar)。

    现在再来定义一下函数的详细递归描述形式。假设我们需要定义一个函数findMedian，从前面讨论里可以看到，用递归的方式来描述算是一种比较直接的方法。它的定义方式可以是double findMedian(int[] a, int al, int ar, int[]b, int bl, int br, int k)。这里参数int[]a, int[]b比较简单，就是这两个数组。而al, bl分别表示从数组a, b里当前搜索的起始索引点。而ar, br表示什么呢？一种描述方式是它们定义a,b 两个数组里搜索的结束索引点。还有一种方式是它们定义a, b两个数组里相对起始索引到数组末尾的距离。虽然它们都可以表达同样的意思，但是在代码的实现细节里会有点差别。这里我们先假设用ar, br来表示起始索引到数组末尾的距离。而最后面的k则表示相对于数组a, b来说，目标元素所处的位置。根据这些讨论，我们可以确定一个它们递归关系的伪代码如下：

    

public double findMedian(int[] a, int al, int ar, int[] b, int bl, int br, int k) {
    //取 k / 2作为起始比较点
    int pa = Math.min(k / 2, ar);
    int pb = k - pa;
    // 根据pa, pb两个点确定比较元素的位置
    if(a[al + pa -1] == b[bl + pb - 1]) {
        // 两个元素相等，正好是我们期望的结果，返回任意一个即可。
        return a[al + pa - 1];
    } else if(a[al + pa - 1] > b[bl + pb - 1]) {
        /* 数组a里的元素大于对应数组b中间的元素，缩小b数组的搜索范围，
        搜索起始点为b[bl + pb],对应的k位置的元素为k - pb。
        */
        return findMedian(a, al, ar, b, bl + pb, br - pb, k - pb);
    } else {
         // 数组a里的元素小于对应数组b中间的元素，缩小a数组的搜索范围
         return findMedian(a, al + pa, ar - pa, bl, br, k - pa);
    }
}

     上述代码的这个递归关系要推导出来还是挺不容易的。有了这个关系之后，剩下需要考虑的就是递归退出的情况了。一种情况是一个数组本身的长度就是0，这样的话只要取另外一个数组里的k - 1的位置就可以了。在针对这个条件的具体实现上可以首先做一个判断，将两个数组中长度端的那个放到前面的参数里，然后再应用这个判断作为退出条件。

    还有一种情况就是当我们递归到k == 1的时候，这个时候对于数组a, b来说，只需要取a[al], b[bl]里比较小的那个值返回就可以了。

    这样，经过这么一通艰苦的讨论，我们可以得到一个如下的代码： 

 

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 == 1) 
            return findMedian(A, 0, m, B, 0, n, total / 2 + 1);
        else 
            return (findMedian(A, 0, m, B, 0, n, total / 2) + 
                findMedian(A, 0, m, B, 0, n, total / 2 + 1)) / 2.0;
    }
    
    private double findMedian(int[] a, int al, int ar, int[] b, int bl, int br, int k) {
        if(ar > br) return findMedian(b, bl, br, a, al, ar, k);
        if(ar == 0) return b[bl + k - 1];
        if(k == 1) return Math.min(a[al], b[bl]);
        int pa = Math.min(k / 2, ar);
        int pb = k - pa;
        if(a[al + pa - 1] == b[bl + pb - 1]) 
            return a[al + pa - 1];
        else if(a[al + pa - 1] < b[bl + pb - 1]) 
            return findMedian(a, al + pa, ar - pa, b, bl, br, k - pa);
        else 
            return findMedian(a, al, ar, b, bl + pb, br - pb, k - pb);
    }
}

   

    非递归版本：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if(m > n) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
            int tempVal = m;
            m = n;
            n = tempVal;
        }
        
        int mid = (m + n + 1) / 2;
        int l = 0, r = m;
        while (l <= r) {
            int i = (l + r) / 2;
            int j = mid - i;
            if(i < r && nums2[j - 1] > nums1[i]) {
                l = i + 1; 
            } else if (i > l && nums1[i - 1] > nums2[j]) {
                r = i - 1;
            } else {
                int maxLeft;
                if (i == 0) {
                    maxLeft = nums2[j - 1];
                } else if(j == 0) {
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }
                int minRight;
                if(i == m) {
                    minRight = nums2[j];
                } else if(j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums1[i], nums2[j]);
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}

 

 

总结

     查找两个排序数组的中间值看起来比较容易，但是要达到一个时间复杂度为O(logN)的方法并能定义清楚它们的递归关系还是很麻烦的。这里递归的参数选择也比较重要，很多细节值得反复揣摩。

 

参考材料

http://www.drdobbs.com/parallel/finding-the-median-of-two-sorted-arrays/240169222

http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/

http://www.geeksforgeeks.org/median-of-two-sorted-arrays/

http://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/