计算机

LeetCode: Median of Two Sorted Arrays解题报告

汤米留下评论

老早进看过这道题了，看见时间复杂度的要求是O(log(m+n))就确定应该和二分查找有关。刚拿到题目的时候，稍微想了想感觉有点麻烦，又有些忌惮“Hard”难度，就放着一直没做。最近在网上搜了搜解题报告，发现沿着http://www.cnblogs.com/TenosDoIt/p/3554479.html的思路做下去，只要把各种情况分析清楚了，其实不是很复杂（我反正是没有一次性全部想清楚，WA了好几次。不过发现不同情况可以互相转换，所以改动不大就过了。。）。以下是做此题的“心路历程”，非典型解题报告：

首先是沿着“删除数”的思路，每次取两个数组内位于[m/2]和[n/2]的数进行比较，删除位于合并后数组两侧相等数量的元素。为了简便操作，我们先假设m<=n（如果不满足，则先交换两个数组），这样每次删除的元素个数则是[m/2]。

按照此流程递归下去，边界条件是什么呢？那就是m==1的时候，你需要考虑nums1剩下的这个数安插进nums2剩下的数里的什么位置，就可以确定中位数怎么计算了。

第一次尝试提交，发现华丽的WA了。仔细一想，发现上面的方法漏掉了一种情况。上面的算只考虑了以下情况：

  1. 中位数只有一个
  2. 中位数是两个数的平均值，且至少有一个数在nums2中

漏掉的一种情况：

  1. 中位数是两个数的平均值，且两个数都在nums1中

这种情况下，当nums1中元素个数为偶数时，如果按照之前的方法，会删掉其中一个本应参与中位数计算的数（nums1为奇数的时候，被删除的数为[m/2]，刚好不会删到这个数）。而另一方面，一旦这种情况出现，也就是参与中位数计算的两个数都位于nums1中， 当前nums1的中位数正好就是这两个数，那么这两个数的大小也必然位于nums2目前的中位数之间，那也就不用递归下去了，直接返回结果即可。

修改后又提交了一次，还是WA了，一看数据是[1,4],[2,3]。原来是因为4>3，导致删掉了2和4。而如果是[2,3],[1,4]的顺序的话，则不会有问题。也就是说当m=n的时候，需要保证nums1[m/2]<nums2[n/2]时，才继续递归下去，否则需交换两个数组。 改了这一处之后就AC了。最后附上渣渣代码：

double findMedian(int* a1, int n1, int* a2, int n2) {
    if (n1 &gt; n2) return findMedian(a2, n2, a1, n1);
    int m1 = n1 &gt;&gt; 1, m2 = n2 &gt;&gt; 1;
    if (n1 == n2 &amp;&amp; a1[m1] &gt; a2[m2]) return findMedian(a2, n2, a1, n1);
    if (n1 == 0)
        if (n2 % 2 == 0) return (a2[m2 - 1] + a2[m2]) / 2.0;
        else return (a2[m2]);
    if (n1 == 1)
        if (n2 == 1) return (a1[0] + a2[0]) / 2.0;
        else if (n2 % 2 == 0)
            if (a1[0] &gt;= a2[m2]) return a2[m2];
            else if (a1[0] &gt;= a2[m2 - 1]) return a1[0];
            else return a2[m2 - 1];
        else
            if (a1[0] &gt;= a2[m2 + 1]) return (a2[m2] + a2[m2 + 1]) / 2.0;
            else if (a1[0] &gt;= a2[m2 - 1]) return (a1[0] + a2[m2]) / 2.0;
            else return (a2[m2 - 1] + a2[m2]) / 2.0;
    else
        if (n1 % 2 == 0 &amp;&amp; n2 % 2 == 0 &amp;&amp; a1[m1 - 1] &gt;= a2[m2 - 1] &amp;&amp; a1[m1] &lt;= a2[m2]) return (a1[m1 - 1] + a1[m1]) / 2.0;
        else if (a1[m1] == a2[m2]) return a1[m1];
        else if (a1[m1] &lt; a2[m2]) return findMedian(a1 + m1, n1 - m1, a2, n2 - m1);
        else return findMedian(a1, n1 - m1, a2 + m1, n2 - m1);
}

class Solution {
public:
    double findMedianSortedArrays(vector&lt;int&gt;&amp; nums1, vector&lt;int&gt;&amp; nums2) {
        return findMedian(nums1.data(), nums1.size(), nums2.data(), nums2.size());
    }
};

留下评论