当分而治之算法达到其极限时会是什么样子？

问题：

一开始看到时间复杂度是O(log(m+n))，我立刻就想到了减半的方法，是的，但是这道题我们得到了两个。块。当两个数组的长度之和为奇数或偶数时，我们该如何处理？什么情况下进行减半？如何分享？我们必须考虑到这一点。

1。中位数是多少？

首先我们来说一下中位数的概念：n个数字是有序的。

• 如果 n 为奇数，则中位数为 (n+1)/2。数，即中间的数。
• 如果 n 是偶数，则中位数为 n/2。数和数 n/2 + 1 的算术平均值。

2。我们如何处理数组总长度为奇数和偶数的情况？

假设总长度为n，求(n+1)/2。数，然后 (n+2)/2。 number（注：索引值均向下舍入）。然后求两个数的平均值，这就是最终需要的中位数。这适用于奇数和偶数。

3。什么情况下我们应该把它分成两部分？怎么能分成两部分呢？

回到原来问题的起点，我们想要找到某个特定位置上的数字，那么想一想如何排除那些肯定不属于该位置的数字呢？

例如两个数组：[1,2,4,6,8],[5,7,9,11]。总长度为9，中位数为5。用一个数组很容易处理，但现在我们有两个数组。我们用更巧妙的方法得到数字5：

• 1。步骤：转换 5/2 ，向下舍入 2。比较两个数组的第二个数字对应于 2 和 7。显然前者比后者小，所以现在直接删除第一个数组的前2个数字，因为它们100%在中位数之前。
• 2。第 1 步：现在我们已经确定了前两个数字，我们将从以下数字中询问第三个数字。按照前面的方法，3/2，四舍五入为1，比较两个数组的第一个数，分别对应4和5，前者比后者小，直接去掉第一个数组的第一个数，因为100 %在中位数之前，不需要考虑。
• 3。步骤1：好的，现在我们已经确定了前三个数字，我们将从下面的数字中询问第二个数字。按照上面的方法，我们淘汰了5个。
• 4。第 1 步：现在我们已经确定了前四个数字，我们需要以下数字中的第一个。直接比较当前两个数组的第一个数。 6

问题的概括就是获取第k个数，比较两个数组中的第k/2个数，如果较小，则将数组的前k/2个元素全部移除，并按顺序执行循环。直到 k 为 1 或其中一个数组为空。

4。如果 k/2 大于一个数组的长度怎么办？

这种情况下，我们只需要取出数组末尾的元素即可。

5。显示JS代码

代码为：

//找到第k大的元素
const findKMax = (num1, start1, end1, num2, start2, end2, k) => {
    let len1 = end1 - start1 + 1;
    let len2 = end2 - start2 + 1;
    //这里我是来保证num1的长度一定小于num2,这样确定num1为空，直接来取num2的第k个数
    if (len1 > len2)
        return findKMax(num2, start2, end2, num1, start1, end1, k);
    if (len1 == 0) return num2[start2 + k - 1];

    if (k == 1) return Math.min(num1[start1], num2[start2]);
    // |0这个操作为向下取整
    //如果k/2比其中一个数组的长度还要大,取数组末尾元素即可
    let i = start1 + Math.min(len1, k / 2 | 0) - 1;
    let j = start2 + Math.min(len2, k / 2 | 0) - 1;

    if (num1[i] > num2[j])
        //已经剔除j - start2 + 1个元素
        return findKMax(num1, start1, end1, num2, j + 1, end2, k - (j - start2 + 1));
    else
        //已经剔除i - start1 + 1个元素
        return findKMax(num1, i + 1, end1, num2, start2, end2, k - (i - start1 + 1));
}
//核心函数
const findMedianSortedArrays = (nums1, nums2) => {
    let m = nums1.length;
    let n = nums2.length;
    //向下取整
    let left = (m + n + 1) / 2 | 0;
    let right = (m + n + 2) / 2 | 0;
    
    //处理了数组总长度为奇数和偶数的情况
    return (findKMax(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, left) +
        findKMax(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, right)) * 0.5;
}
复制代码

AC成功！

作者：沉三元
链接：https://juejin.im/post/5d7b051ef265da03925a7515
来源：掘金
版权归作者所有。商业转载请联系作者获得许可。非商业转载请注明来源。